Mr. Black recently bought a villa in the countryside. Only one thing
bothers him: although there are light switches in most rooms, the lights
they control are often in other rooms than the switches themselves.
While his estate agent saw this as a feature, Mr. Black has come to
believe that the electricians were a bit absent-minded (to put
it mildly) when they connected the switches to the outlets.
One night, Mr. Black came home late. While standing in the hallway,
he noted that the lights in all other rooms were switched off.
Unfortunately, Mr. Black was afraid of the dark, so he never dared to enter
a room that had its lights out and would never switch off the lights
of the room he was in.
After some thought, Mr. Black was able to use the incorrectly wired
light switches to his advantage. He managed to get to his bedroom and to
switch off all lights except for the one in the bedroom.
You are to write a program that, given a description of a villa,
determines how to get from the hallway to the bedroom if only the hallway
light is initially switched on. You may never enter a dark room, and after
the last move, all lights except for the one in the bedroom must
be switched off. If there are several paths to the bedroom, you have
to find the one which uses the smallest number of steps,
where ``move from one room to another'', ``switch on a light''
and ``switch off a light'' each count as one step.
The input file contains several villa descriptions. Each villa starts
with a line containing three integers r, d, and s. r is the number of
rooms in the villa, which will be at most 10. d is the number of
doors/connections between the rooms and s is the number of light switches
in the villa. The rooms are numbered from 1 to r; room number 1 is
the hallway, room number r is the bedroom.
This line is followed by d lines containing two integers i and j each,
specifying that room i is connected to room j by a door.
Then follow s lines containing two integers k and l each,
indicating that there is a light switch in room k that controls the
light in room l.
A blank line separates the villa description from the next one. The input
file ends with a villa having r = d = s = 0, which should not be processed.
For each villa, first output the number of the test
case (`Villa #1', `Villa #2', etc.) in a line of its own.
If there is a solution to Mr. Black's problem, output the shortest
possible sequence of steps that leads him to his bedroom and only leaves
the bedroom light switched on. (Output only one shortest sequence if you find
more than one.) Adhere to the output format shown in the sample below.
If there is no solution, output a line containing the statement
`The problem cannot be solved.'
Output a blank line after each test case.
3 3 4
1 2
1 3
3 2
1 2
1 3
2 1
3 2
2 1 2
2 1
1 1
1 2
0 0 0
Villa #1
The problem can be solved in 6 steps:
- Switch on light in room 2.
- Switch on light in room 3.
- Move to room 2.
- Switch off light in room 1.
- Move to room 3.
- Switch off light in room 2.
Villa #2
The problem cannot be solved.
題目描述:
這先生很怕黑,回到家時第一個房間燈會亮,然後靠著這房間內部的開關,開啟別的房間的電燈,
而別的房間也會有其他房間的開關,則最後要回到寢室。
一路上只能進入有已經開燈的房間,而最後回到寢室時,除了寢室外的房間燈都必須關閉。
題目解法:
狀態壓縮+bfs。
狀態壓縮所有房間開關燈的資訊,以及當前在哪一個點。
最後進行回朔輸出答案。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> g[15], turn[15];
int dp[15][2048], argdp[15][2048];
void bfs(int n) {
memset(dp, 0, sizeof(dp));
dp[1][1] = 1;
int tn, mark, i;
queue<int> Q, M;
Q.push(1), M.push(1);
while(!Q.empty()) {
tn = Q.front(), Q.pop();
mark = M.front(), M.pop();
for(i = 0; i < g[tn].size(); i++) {//move
if(((mark>>(g[tn][i]-1))&1) && dp[g[tn][i]][mark] == 0) {
dp[g[tn][i]][mark] = dp[tn][mark]+1;
argdp[g[tn][i]][mark] = tn;
Q.push(g[tn][i]), M.push(mark);
}
}
for(i = 0; i < turn[tn].size(); i++) {//switch
if(dp[tn][mark^(1<<(turn[tn][i]-1))] == 0) {
dp[tn][mark^(1<<(turn[tn][i]-1))] = dp[tn][mark]+1;
argdp[tn][mark^(1<<(turn[tn][i]-1))] = -turn[tn][i];
Q.push(tn), M.push(mark^(1<<(turn[tn][i]-1)));
}
}
}
if(dp[n][1<<(n-1)] == 0) {
puts("The problem cannot be solved.");
return;
}
printf("The problem can be solved in %d steps:\n", dp[n][1<<(n-1)]-1);
int ret[1000][2], idx = 0;
tn = n, mark = 1<<(n-1);
while(tn != 1 || mark != 1) {
if(argdp[tn][mark] > 0) {
ret[idx][0] = tn;
ret[idx][1] = 0;//move
idx++;
tn = argdp[tn][mark];
} else {
argdp[tn][mark] *= -1;
ret[idx][0] = argdp[tn][mark];
if((mark>>(argdp[tn][mark]-1))&1)
ret[idx][1] = 1;// open
else
ret[idx][1] = 2;// close
idx++;
mark ^= (1<<(argdp[tn][mark]-1));
}
}
for(i = idx-1; i >= 0; i--) {
if(ret[i][1] == 0) {
printf("- Move to room %d.\n", ret[i][0]);
} else if(ret[i][1] == 1) {
printf("- Switch on light in room %d.\n", ret[i][0]);
} else
printf("- Switch off light in room %d.\n", ret[i][0]);
}
}
int main() {
int r, d, s;
int i, j, k, x, y;
int cases = 0;
while(scanf("%d %d %d", &r, &d, &s) == 3 && r) {
for(i = 1; i <= r; i++)
g[i].clear(), turn[i].clear();
for(i = 0; i < d; i++) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
for(i = 0; i < s; i++) {
scanf("%d %d", &x, &y);
if(x == y) continue;
turn[x].push_back(y);
}
printf("Villa #%d\n", ++cases);
bfs(r);
puts("");
}
return 0;
}
文章定位: