ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 0172 Doctor's Research Rooms

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0172


・概要
部屋の電気をすべて消して部屋をでることができるか判定する問題です。


・解法
幅優先探索(bfs)で解くことができます。

個人的な意見ですが、この問題は無駄な処理をちゃんと省いていかないとすぐTLEになってしまうので、枝刈りをしっかりしましょう。

明かりの点灯情報情報をビットで持たせたり、出力すべき文字列をあらかじめ全通り作っておくとよいです。
そこでとても活躍したのが、sprintfです。

char tmp[50];
sprintf(tmp, "Switch on room %d.",j);
table[0][j] = string(tmp);

このようにすることで、文字列と数字が合わさった文字列を出力したいとき一発でできます、便利!!


ソースコード

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define f first
#define s second
#define mp make_pair
typedef pair<int, int> P;
static const int INF = (1 <<29);

struct State{
   int pos;
   int light;
   vector<P> step;
   
   State(){}
   State(int p, int l, vector<P> s):pos(p),light(l),step(s){}
};

//light : 1 = ON, 0 = OFF
int n,m;
int initLight;
vector<int> edge[16], room[16];
int minStep[15][(1 << 15)];
bool exitFlag;
string table[3][16];//0 = ON, 1 = OFF, 2 = MOVE

void makeTable(){
   char tmp[50];
   for(int j = 1 ; j <= 15 ; j++){
     sprintf(tmp, "Switch on room %d.",j);
     table[0][j] = string(tmp);
     sprintf(tmp, "Switch off room %d.",j);
     table[1][j] = string(tmp);
     sprintf(tmp, "Move to room %d.",j);
     table[2][j] = string(tmp);
   }
}

void bfs(){
   rep(i,15)rep(j,(1 << 15))minStep[i][j] = INF;
   exitFlag = false;
   int goal = (1 << (n-1)) ;
   queue<State> q;
   q.push(State(0, initLight, vector<P>()));
   
   while(!q.empty()){
      State p = q.front();
      q.pop();
    
      if(p.pos==n){
	 // Case 1
	 if(p.light == goal){
	    cout << "You can go home in " << p.step.size() << " steps." << endl;
	    for(int i = 0 ; i < p.step.size() ; i++){
	       cout << table[p.step[i].f][p.step[i].s] << endl;
       	    }
	    return;
	 }
	 // Case 2
	 else{
	    exitFlag = true;
	    continue;  
	 }
      }
      
      if(minStep[p.pos][p.light] <= p.step.size())continue;
      minStep[p.pos][p.light] = p.step.size();
    
      for(int j = 0 ; j < room[p.pos].size() ; j++){
	 int tmpLight = p.light;
	 vector<P> tmpStep = p.step;
	 
         //照明がついているので、消す。
	 if(((p.light >> room[p.pos][j]) & 1) && p.pos != room[p.pos][j]){
	    tmpLight -= (1 << room[p.pos][j]);
	    tmpStep.push_back(mp(1, room[p.pos][j]+1));
	 }

	 //照明がついていないので、つける。
	 if(((p.light >> room[p.pos][j]) & 1)==0){    
	    tmpLight += (1 << room[p.pos][j]);
	    tmpStep.push_back(mp(0, room[p.pos][j]+1));
	 }

	 if(minStep[p.pos][tmpLight] > tmpStep.size()) q.push(State(p.pos, tmpLight, tmpStep));
      }

      for(int to = 0 ; to < edge[p.pos].size() ; to++){
	 if(p.pos==n-1){
	    q.push(State(edge[p.pos][to], p.light, p.step));
	 }
         //次の部屋の照明がついているので進むことができる。
	 if((p.light >> edge[p.pos][to]) & 1){
	    vector<P> tmpStep = p.step;
	    tmpStep.push_back(mp(2, edge[p.pos][to]+1));
	    if(minStep[edge[p.pos][to]][p.light] > tmpStep.size()) q.push(State(edge[p.pos][to], p.light, tmpStep));
	 }
      }
   }
  
   // Case 2
   if(exitFlag) cout << "You can not switch off all lights." << endl;
   // Case 3
   else cout << "Help me!" << endl;
}

void init(){
   initLight = 0;
   
   for(int i = 0 ; i < 16 ; i++){
      edge[i].clear();
      room[i].clear();
   }
   
   edge[n-1].push_back(n);
}
   
int main(){
   makeTable();
   while(cin >> n >> m){
      if(n==0 && m==0)break;

      init();

      //input
      for(int i = 0 ; i < m ; i++){
	 int s,t;
	 cin >> s >> t;
	 s--; t--;
	 edge[s].push_back(t);
	 edge[t].push_back(s);
      }

      for(int i = 0 ; i < n ; i++){
	 int v;
	 cin >> v;
	 if(v==1) initLight |= (1 << i);
      }
       
      for(int i = 0 ; i < n ; i++){
	 int k;
	 cin >> k;
	 for(int j = 0 ; j < k ; j++){
	    int v;
	    cin >> v;
	    v--;
	    room[i].push_back(v);
	 }
	 sort(room[i].begin(), room[i].end());
      }

      bfs();
   }
   return 0;
}