uva321 bfs搜尋

這道題系統沒法送出，是以不知道能否AC，但我感覺程式沒啥問題，比較簡單，可以跑幾個測試用例比對一下。

題意容易了解，思路 是将所在的房間号和r個房間的開燈情況作為一個狀态，這樣最多會有10*2^10種狀态，并不多。然後就是bfs寬度周遊了，要注意一點是人在某個房間中不可以把該房間的燈關上，是以我在輸入的燈開關數組時候就做了一個判斷，如果兩個數字相同，也即控制該房間燈的開關就在這個房間時，開關是無效的（很不符合常理~~）這樣就保證了之後開關燈的合法性。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAXSIZE = 60000;
const int N=11;

struct state
{
	int room[N];
	int location,behave;
};

int r,d,s,front,rear,step,prestate[MAXSIZE];
bool flag,door[N][N],swit[N][N],vis[N][1025];
state target,S[MAXSIZE];
void init()
{
	memset(swit,0,sizeof(swit));
	memset(door,0,sizeof(door));
	memset(S,0,sizeof(S));
	memset(vis,0,sizeof(vis));
	S[0].room[1]=1;
	S[0].location=1;
	vis[1][1]=1;
	target.location=r;
	memset(target.room,0,sizeof(target.room));
	target.room[r]=1;
}
int caldex(state s)
{
	int dex=0,exp=1;
	for (int i=1;i<=r;i++)
	{
		dex=dex+s.room[i]*exp;
		exp=exp << 1 ;
	}
	return dex;
}
bool compare(state s)
{
	if (s.location==target.location)
	{
		for (int i=1;i<=r;i++)
		{
			if (s.room[i]!=target.room[i])
				return 0;
		}
		return 1;
	}
	return 0;
}
void bfs()
{
	front=0;rear=1,step=0,flag=0;
	while (front<rear)
	{
		step++;
		int tmprear=rear;
		while (front<tmprear)
		{
			state cs = S[front];
			int i;
			for (i=1;i<=r;i++)
			{
				if (swit[cs.location][i])
				{
					state &ns = S[rear];
					ns=S[front];
					ns.room[i]=!ns.room[i];
					if (compare(ns))
					{
						flag=1;
						prestate[rear]=front;
						ns.behave=i*10+(ns.room[i]==1?1:2);		//1:turn on;2:turn off
						return;
					}
					int dex=caldex(ns);
					if (!vis[ns.location][dex])
					{
						vis[ns.location][dex]=1;
						prestate[rear]=front;
						ns.behave=i*10+(ns.room[i]==1?1:2);		//1:turn on;2:turn off
						rear++;
					}
				}
			}
			for (i=1;i<=r;i++)
			{
				if (door[cs.location][i]&&cs.room[i])
				{
					state &ns=S[rear];
					ns=cs;
					ns.location=i;
					int dex=caldex(ns);
					if (!vis[ns.location][dex])
					{
						vis[ns.location][dex]=1;
						prestate[rear]=front;
						ns.behave=3*100+i;		
						rear++;
					}
				}
			}
			front++;
		}
	}
}
void print(state s)
{
	cout<<"- ";
	if (s.behave>300)
	{
		cout<<"Move to room "<<s.behave%300<<"."<<endl;
	}
	else
	{
		if (s.behave%10==1)
		{
			cout<<"Switch on light in room "<<s.behave/10<<"."<<endl;
		}
		else
		{
			cout<<"Switch off light in room "<<s.behave/10<<"."<<endl;
		}
	}
}
int main()
{
	int col=0;
	while (cin>>r>>d>>s&&r)
	{
		col++;
		init();
		for (int i=0;i<d;i++)
		{
			int m,n;
			cin>>m>>n;
			door[m][n]=door[n][m]=1;
		}
		for (int i=0;i<s;i++)
		{
			int m,n;
			cin>>m>>n;
			if (m!=n)
				swit[m][n]=1;
		}
		bfs();
		cout<<"Villa #"<<col<<endl;
		if (flag)
		{
			cout<<"The problem can be solved in "<<step<<" steps:"<<endl;
			int *result = new int[step];
			int pre=rear;
			for (int i=0;i<step;i++)
			{
				result[i]=pre;
				pre=prestate[pre];
			}
			for (int j=step-1;j>=0;j--)
			{
				print(S[result[j]]);
			}
			delete result;
		}
		else cout<<"The problem cannot be solved."<<endl;
		cout<<endl;
		getchar();
	}
	return 0;
}