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;
}

沒有留言:

張貼留言