Problem 0172 : Doctor's Research Rooms

Doctor's Research Rooms
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0172

• 問題概要

暗いところが怖い教授。
彼は電気がついてない部屋に入れない。
部屋の数と部屋同士がつながってるドアが与えられる。
今、どの部屋が電気が付いてるかあたえられる。
どの部屋からどの部屋の電気を操作できるかあたえられる。
電気をうまく操作して出口にたどり着けるのか？？
さらに、出口の電気以外を消して出口に辿りつけるのか？？
できるなら手順をだせ。
という問題。

• 解法

BFS。
パスを出す必要があるのがネック。
最後に出力するstringごと生成しながらBFSすると間に合わない。
だから、intで履歴をもつ。
１桁目が移動３桁目がスイッチをおした　とか、そういうふうに。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

class State{
public:
  bool sw[15];
  int pos;
  vector<int> history;
  State(){
    rep(i, 15)sw[i] = false;
  }
  bool operator < (const State &s)const{
    if(pos != s.pos)return pos < s.pos;
    rep(i, 15)if(sw[i] != s.sw[i])return sw[i] < s.sw[i];
    return false;
  }
  void turn(int r){
    sw[r] = !sw[r];
    int tmp = 0;
    if(sw[r])tmp += 10000;
    tmp += r * 100;
    history.pb(tmp);
  }
  void move(int to){
    pos = to;
    history.pb(to+1);
  } 
};

bool down(State s, int n){
  rep(i, n-1){
    if(s.sw[i])return false;
  }
  return true;
}

string whatdone(int his){
  stringstream sin;
  if(his % 100 != 0){
    sin << "Move to room " << his << '.';
  }
  else{
    sin << "Switch ";
    if(his>=10000)sin << "on room ";
    else sin << "off room ";
    sin << (his%10000)/100 + 1<< '.';
  }
  return sin.str(); 
}

void out(State s){
  cout << "You can go home in "<< s.history.size()<< " steps." << endl;
  rep(i, s.history.size()){
    cout << whatdone(s.history[i]) << endl;
  }
}


main(){
  int n, m;
  while(cin >> n >> m){
    if(n + m == 0)break;
    int edge[n][n];
    rep(i, n)rep(j, n)edge[i][j] = false;
    rep(i, m){
      int s, t;
      cin >> s >> t;
      s--;t--;
      edge[s][t] = edge[t][s] = true;
    }
    State start;
    rep(i, n){
      int tmp;
      cin >> tmp;
      start.sw[i] = (tmp == 1);
    }
    vint SW[n];
    rep(i, n){
      int sw;
      cin >> sw;
      rep(j, sw){
	int tmp;
	cin >> tmp;
	tmp--;
	SW[i].pb(tmp);
      }
      sort(ALL(SW[i]));
    }
    start.pos = 0;
    queue<State> Q;
    set<State> S;
    Q.push(start);
    S.insert(start);
    bool flag = false, no = true;
    while(!Q.empty()){
      State s = Q.front();Q.pop();
      if(s.sw[s.pos] == false)continue;
      if(s.pos == n - 1){
	flag = true;
	no = false;
	if(down(s, n)){
	   out(s);
	  flag = false;
	  no = false;
	  break;
	}
      }
      rep(i, SW[s.pos].size()){
	State next = s;
	next.turn(SW[s.pos][i]);
	if(S.find(next) == S.end()){
	  S.insert(next);
	  Q.push(next);
	}
      }
      rep(i, n){
	if(edge[s.pos][i] && s.sw[i]){
	  State next = s;
	  next.move(i);
	  if(S.find(next) == S.end()){
	    S.insert(next);
	    Q.push(next);
	  }
	}
      }
    }
    if(no)cout<<"Help me!" << endl;
    if(flag)cout << "You can not switch off all lights."<<endl;
  }
}