321

I used bit operation to represent the states of the switches state of the villa.

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <sstream>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;

struct Point{
	int x,y;
};
int kase=1;
Point points[11500];
int arr[11][1024];
int array_map_par[11500];
bool door[15][15];
bool light_swtch[15][15];
bool flag;
int RR,DD,SS;
int gr[11][1024];

int checkbit(int num,int idx)
{
	return (num&(1<<(idx-1)));
}
void bfs()
{
	int bit;
	vector<string> vb;
	string str[11500];
	queue<int> q;
	int step;
	gr[1][1]=1;
	q.push(1);q.push(1);q.push(0);
	while(!q.empty())
	{
		int rum=q.front();q.pop();
		int res=q.front();q.pop();
		int status_vila = res;
		int num=res;
		int parent_index = arr[rum][res];
		step=q.front();q.pop();
		if(rum==RR && res==(1<<(RR-1)))
		{
			printf("Villa #%d\nThe problem can be solved in %d steps:\n",kase++,step);

			flag=1;
			while(array_map_par[parent_index]!=-1)
			{
				vb.push_back(str[parent_index]);
				parent_index = array_map_par[parent_index];
			}
			for(int II=vb.size()-1;II>=0;II--)
			cout<<vb[II];
			return;
		}
		for(int i=1;i<=RR;i++)
		{
			if(light_swtch[rum][i])
			{
				bit=checkbit(res,i);
				if(bit==0)
				{
					status_vila = res | (1<<(i-1));
					if(gr[rum][status_vila]==0)
					{
						gr[rum][status_vila]=1;
						q.push(rum);q.push(status_vila);
						q.push(step+1);
						array_map_par[arr[rum][status_vila]]=parent_index;
						str[arr[rum][status_vila]]="- Switch on light in room ";
						if(i<10)
						str[arr[rum][status_vila]].append(1u,char(i+'0'));
						else
							str[arr[rum][status_vila]].append("10");
						str[arr[rum][status_vila]].append(".\n");
					}
				}
				else
				{
					status_vila = res & (~(1<<(i-1)));
					if(gr[rum][status_vila]==0 && rum!=i)//cant switch off the room where he is in
					{
						gr[rum][status_vila]=1;
						q.push(rum);q.push(status_vila);
						q.push(step+1);
						array_map_par[arr[rum][status_vila]]=parent_index;
						str[arr[rum][status_vila]]="- Switch off light in room ";
						if(i<10)
							str[arr[rum][status_vila]].append(1u,char(i+'0'));
						else
							str[arr[rum][status_vila]].append("10");
						str[arr[rum][status_vila]].append(".\n");
					}
				}

			}
		}
		int rum_index=0;
		while(num)
		{
			rum_index+=1;
			bit = (num&1);
			num=(num>>1);
			if(door[rum][rum_index]==0)
			continue;
			if(bit)
			{
				if(gr[rum_index][res]==0)
				{
					gr[rum_index][res]=1;
					q.push(rum_index);q.push(res);
					q.push(step+1);
					array_map_par[arr[rum_index][res]]=parent_index;
					str[arr[rum_index][res]]="- Move to room ";
					if(rum_index<10)
					str[arr[rum_index][res]].append(1u,char(rum_index+'0'));
					else
					str[arr[rum_index][res]].append("10");
					str[arr[rum_index][res]].append(".\n");

				}
			}
		}

	}

}

void _init()
{
	int cnt=1;
	for(int i=1;i<11;i++)
	{
		for(int j=1;j<1024;j++)
		{
			points[cnt].x=i;points[cnt].y=j;
			arr[i][j]=cnt;cnt+=1;
		}
	}
}
int main()
{
	int a,b;
	_init();
	while(scanf("%d%d%d",&RR,&DD,&SS))
	{
		if(RR+DD+SS==0)
		break;
		memset(door,0,sizeof(door));
		memset(gr,0,sizeof(gr));
		memset(light_swtch,0,sizeof(light_swtch));
		memset(array_map_par,-1,sizeof(array_map_par));

		for(int i=1;i<=DD;i++)
		{
			scanf("%d%d",&a,&b);door[a][b]=1;door[b][a]=1;
		}
		for(int i=1;i<=SS;i++)
		{
			scanf("%d%d",&a,&b);light_swtch[a][b]=1;
		}
		flag=0;
		bfs();
		if(!flag)
		printf("Villa #%d\nThe problem cannot be solved.\n\n",kase++);
		else
		printf("\n");

	}
	return 0;
}