0172-Doctor's Research Rooms

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0172&lang=jp
幅優先探索。
状態数は各部屋の照明のONOFFと現在の部屋のぶんだけあるのでO(n 2^n)
自分がいる部屋のライトは消さないということを失念していて一度Wrong Answerになった。
出力にはsprintfが大活躍した。

実装(C++)

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <deque>
using namespace std;
int door[15][15];
int swi[15];
vector<int> lightstate[15];
int n,m;
typedef pair<int,int> state;
state back[15][1<<15];
int accessed[15][1<<15];
void outputswitch(deque<string>& res,int back,int next){
	char tmp[150];
	for(int i=n-1;i>=0;i--){
		if(((back^next)>>i)&1){
			if((back>>i)&1){
				sprintf(tmp,"Switch off room %d.",i+1);
				res.push_front(string(tmp));
			}else{
				sprintf(tmp,"Switch on room %d.",i+1);
				res.push_front(string(tmp));
			}
		}
	}
}
void solve(int light){
	state t;t.first=0;t.second=light;
	bool goal=false;
	int nl;
	queue<state> que;que.push(t);
	memset(accessed,0,sizeof(accessed));
	back[0][light].first=-1;
	back[0][light].second=-1;
	accessed[0][light]=1;
	while(!que.empty()){
		t=que.front();que.pop();
		if(t.first==n-1){
			goal=true;
			for(unsigned int i=0;i<lightstate[t.first].size();i++){
				nl=t.second^lightstate[t.first][i];
				if((nl&((1<<(n-1))-1))==0){
					deque<string> res;
					outputswitch(res,t.second,nl);
					state tt=t;
					char tmp[150];
					while(back[tt.first][tt.second].first>=0){
						sprintf(tmp,"Move to room %d.",tt.first+1);
						res.push_front(tmp);
						outputswitch(res,back[tt.first][tt.second].second,tt.second);
						tt=back[tt.first][tt.second];
					}
					sprintf(tmp,"You can go home in %d steps.",res.size());
					cout << tmp << endl;
					while(!res.empty()){
						cout << res.front() << endl;
						res.pop_front();
					}
					return;
				}
			}
		}
		for(unsigned int i=0;i<lightstate[t.first].size();i++){
			nl=t.second^lightstate[t.first][i];
			if((nl&(1<<t.first))==0)continue;
			for(int j=0;j<n;j++){
				if((nl&(1<<j))>0){
					if(door[t.first][j]>0){
						if(accessed[j][nl]==0){
							que.push(state(j,nl));
							back[j][nl].first=t.first;
							back[j][nl].second=t.second;
							accessed[j][nl]=1;
						}
					}
				}
			}
		}
	}
	if(goal){
		cout << "You can not switch off all lights." << endl;
	}else{
		cout << "Help me!" << endl;
	}
	return;

}
int main() {
	int s,t,light;
	for(;;){
		cin >> n >> m;if(n==0)break;
		memset(door,0,sizeof(door));memset(swi,0,sizeof(swi));
		for(int i=0;i<m;i++){
			cin >> s >> t;s--;t--;door[s][t]=1;door[t][s]=1;
		}
		light=0;
		for(int i=0;i<n;i++){
			cin >> s;
			if(s)light|=1<<i;
		}
		for(int i=0;i<n;i++){
			cin >> s;
			for(int j=0;j<s;j++){
				cin >> t;t--;
				swi[i]|=1<<t;
			}
		}
		for(int i=0;i<n;i++){
			lightstate[i].clear();
		}
		for(int i=0;i<(1<<n);i++){
			for(int j=0;j<n;j++){
				if((swi[j]|i)==swi[j]){
					lightstate[j].push_back(i);
				}
			}
		}
		solve(light);
	}
	return 0;
}