【BFS】The New Villa

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
//#include<cmath>

using namespace std;
const int INF = 9999999;
#define LL long long

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;
	return x*f;
}
int R,D,S;//room door switch
bool vis[10024][13]; 
int a,b;
struct data{
	int seq,st,ro;//状态，步数，现在所在的房间
	bool flag;//0为走路，1为开关灯
	int to;//链表的上一个，前驱
	int turn;//记录当前开关了几号
}Que[100001];
int l=1,r=1;
bool alflag=false;

bool print(data k){
	if(k.to!=-1){//如果不是末尾
		if(!print(Que[k.to])) return 1;//这是防止输出move to 1的
		if(Que[k.to].flag==1){
		   if(Que[k.to].turn>0) printf("- Switch on light in room %d.\n",Que[k.to].turn);//注意on与off的区分输出
		   	else printf("- Switch off light in room %d.\n",-Que[k.to].turn);
		}
		else{
			printf("- Move to room %d.\n",Que[k.to].ro);
		}
		return 1;
	}
	else return 0;
}
vector<int> pat[13];
vector<int> swa[13]; 
int cnt;

void BFS(){
	Que[l].ro=1,Que[l].seq=2,Que[l].st=0;
	Que[l].turn=0;
	Que[l].to=-1;
	if(Que[r].seq==(1<<R)&&Que[r].ro==R){//处理卧室就是走廊的
		alflag=true;
		printf("Villa #%d\n",cnt);
		printf("The problem can be solved in %d steps:\n",Que[r].st);
	    return ;
	}
	int room,Seq,step;
	while(l<=r){
		step=Que[l].st,Seq=Que[l].seq,room=Que[l].ro;
		for(int i=0;i<pat[room].size();i++){//走到另一个房间
			if(((Seq>>pat[room][i])&1)==1&&!vis[Seq][pat[room][i]]){//如果此房间的灯是亮着的且此状态没有出现过
				vis[Seq][pat[room][i]]=true;//标记此状态出现过
				Que[++r].ro=pat[room][i];
				Que[r].st=step+1;
				Que[r].seq=Seq;
				Que[r].to=l;
				Que[r].flag=0;//flag=0表示走路
				if(Que[r].seq==(1<<R)&&Que[r].ro==R){ 
				    alflag=true;
			    	printf("Villa #%d\n",cnt);
					printf("The problem can be solved in %d steps:\n",Que[r].st);
					print(Que[r]);
					printf("- Move to room %d.\n",Que[r].ro);
					return ;
			    }
			}
		}
		for(int i=0;i<swa[room].size();i++){//开/关灯
			if(!vis[Seq^(1<<swa[room][i])][room]&&swa[room][i]!=room){//如果不是此房间的灯且此状态没有出现过的
				vis[Seq^(1<<swa[room][i])][room]=true;
				Que[++r].ro=room;
				Que[r].st=step+1;
				Que[r].seq=Seq^(1<<swa[room][i]);//更改灯亮的状态
				Que[r].to=l;
				Que[r].flag=1; //flag=1表示开关灯
				if(!((Seq>>swa[room][i])&1)) Que[r].turn=swa[room][i];
				else Que[r].turn=-swa[room][i];//负的代表turn off
				if(Que[r].seq==(1<<R)&&Que[r].ro==R){
					alflag=true;
					printf("Villa #%d\n",cnt);
					printf("The problem can be solved in %d steps:\n",Que[r].st);
					print(Que[r]);//递归输出
					if(Que[r].turn>0)
		   				printf("- Switch on light in room %d.\n",Que[r].turn);
		   			else printf("- Switch off light in room %d.\n",-Que[r].turn);
		   			return ;
				}
			}
		}
		l++;//不要忘了这个
	}
}

int main(){
	R=read(),D=read(),S=read();
	while(R!=0||D!=0||S!=0){
		cnt++;
        l=1,r=1;
        for(int i=1;i<=11;i++) pat[i].clear(),swa[i].clear();//注意清空
        memset(vis,0,sizeof(vis));
		for(int i=1;i<=D;i++){
			a=read(),b=read();
			pat[a].push_back(b);//路是双向的，可能走到下一个房间调了一下状态又回来了
			pat[b].push_back(a);
		}
		for(int i=1;i<=R;i++) sort(pat[i].begin(),pat[i].end(),less<int>());//vector排序，因为没有spj
		for(int i=1;i<=S;i++){
			a=read(),b=read();
			swa[a].push_back(b);
		}
		for(int i=1;i<=R;i++) sort(swa[i].begin(),swa[i].end(),less<int>());
		BFS();
		if(!alflag){
			printf("Villa #%d\n",cnt);
			puts("The problem cannot be solved.");
		}
		alflag=false;
		printf("\n");
		R=read(),D=read(),S=read();
	}
	return 0;
}