## 2013年8月29日

### UVa 321 - The New Villa

```#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <map>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

int main() {
int r, d, s, C = 1;
while (scanf("%d%d%d", &r, &d, &s) && r) {
vector<int> con[11];
while (d--) {
int a, b;
scanf("%d%d", &a, &b);
con[a].PB(b);
con[b].PB(a);
}
vector<int> sw[11];
while (s--) {
int a, b;
scanf("%d%d", &a, &b);
sw[a].PB(b);
}
printf("Villa #%d\n", C++);
queue<P> q;
vector<string> path[11][1024];
q.push(MP(1, 1));
bool solved = false;
while (!q.empty()) {
P now = q.front();
q.pop();
int a = now.first, state = now.second;
vector<string> & p = path[a][state];
if (a == r && state == (1 << (r - 1))) {
printf("The problem can be solved in %d steps:\n", p.size());
for (int i = 0; i < p.size(); i++) {
printf("%s\n", p[i].c_str());
}
solved = true;
break;
}
for (int i = 0; i < con[a].size(); i++) {
int b = con[a][i];
if ((state & (1 << (b - 1))) && !path[b][state].size()) {
char temp[99];
sprintf(temp, "- Move to room %d.", b);
path[b][state] = p;
path[b][state].PB(temp);
q.push(MP(b, state));
}
}
for (int i = 0; i < sw[a].size(); i++) {
int b = sw[a][i];
if (a == b) {
continue;
}
int newState = state ^ (1 << (b - 1));
if (!path[a][newState].size()) {
char temp[99];
sprintf(temp, "- Switch %s light in room %d.", (state & (1 << (b - 1))) ? "off" : "on", b);
path[a][newState] = p;
path[a][newState].PB(temp);
q.push(MP(a, newState));
}
}
}
if (!solved) {
puts("The problem cannot be solved.");
}
puts("");
}
return 0;
}
```