#include<iostream>
using namespace std;
char maze[21][21];
int bmaze[20][20];
int keynum[5];
int keyx[5],keyy[5];
int m,n,startx,starty;
int treax,treay;
bool find;
void treasure(int i,int j)
{
	if(bmaze[i][j]==1)
	{
		find=true;
		return;
	}
	else if(maze[i][j]>='a'&&maze[i][j]<='e')
	{
		keynum[maze[i][j]-'a']--;
		if(keynum[maze[i][j]-'a']==0)
		{
			maze[keyx[maze[i][j]-'a']][keyy[maze[i][j]-'a']]='.';
			bmaze[i][j]=0;
		}
			
	}
	bmaze[i][j]=-1;
	maze[i][j]='Y';
	if(!find&&j+1<n&&bmaze[i][j+1]!=-1)
	{
		treasure(i,j+1);
	}
	if(!find&&i+1<m&&bmaze[i+1][j]!=-1)
	{
		treasure(i+1,j);
	}
	if(!find&&j-1>=0&&bmaze[i][j-1]!=-1)
	{
		treasure(i,j-1);
	}
	if(!find&&i-1>=0&&bmaze[i-1][j]!=-1)
	{
		treasure(i-1,j);
	}
}
bool isroad(int i,int j)
{
	if(j+1<n)
	{
		if(maze[i][j+1]=='Y')
			return true;
	}
	if(i+1<m)
	{
		if(maze[i+1][j]=='Y')
			return true;
	}
	if(j-1>=0)
	{
		if(maze[i][j-1]=='Y')
			return true;
	}
	if(i-1>=0)
	{
		if(maze[i-1][j]=='Y')
			return true;
	}
	return false;
}
int main()
{
	int i,j,tap;
	while (cin>>m>>n)
	{
		if(m==0&&n==0) break;
		memset(keynum,0,sizeof(keynum));
		memset(bmaze,0,sizeof(bmaze));
		for (i=0;i<m;i++)
		{
			for (j=0;j<n;j++)
			{
				cin>>maze[i][j];
				if(maze[i][j]=='S')
				{
					startx=i;
					starty=i;
				}
				else if(maze[i][j]>='A'&&maze[i][j]<='E')
				{
					keyx[maze[i][j]-'A']=i;
					keyy[maze[i][j]-'A']=j;
					bmaze[i][j]=-1;
				}
				else if(maze[i][j]>='a'&&maze[i][j]<='e')
				{
					keynum[maze[i][j]-'a']++;
				}
				else if(maze[i][j]=='X')
				{
					bmaze[i][j]=-1;
				}
				else if(maze[i][j]=='G')
				{
					bmaze[i][j]=1;
				}		
			}
		}
		/*for(i=0;i<5;i++)
			cout<<keynum[i]<<" ";
		cout<<endl;*/
		
		find=false;
		while (!find) 
		{
			treasure(startx,starty);
			/*for (i=0;i<m;i++)
			{
				for (j=0;j<n;j++)
				{
					cout<<maze[i][j];
				}
				cout<<endl;
			}
			for(i=0;i<5;i++)
				cout<<keynum[i]<<" ";
			cout<<endl;*/
			if(!find)
			{
				tap=0;
				for (i=0;i<m;i++)
				{
					for (j=0;j<n;j++)
					{
						if ((maze[i][j]=='.')&&isroad(i,j))
						{
							startx=i;
							starty=j;
							tap=1;
							i=m;j=n;
						}
					}
				}
				/*cout<<startx<<" "<<starty<<endl;
				cout<<isroad(3,2)<<endl;
				cout<<"i="<<i<<" j="<<j<<endl;*/
				if(tap==0)
					break;

			}
		}
		if(find)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;	
}

• Re:不知道有什么情况没考虑！ (16) 1272406003 2008-08-02 07:46:13