#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int map[30][30],cnt[300],col[300],sx,sy,m,n;//cnt是地图中要是出现的次数，col是搜索到的要是次数，只要bfs中没有新的节点加入就说明NO
bool vis[30][30];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct NOTE
{
	int x,y;
};
void read()
{
	memset(map,0,sizeof map);
	memset(cnt,0,sizeof cnt);
	memset(col,-1,sizeof col);
	memset(vis,0,sizeof vis);
	char ls[25];
	for(int i=1;i<=m;i++)
	{
		scanf("%s",ls);
		for(int j=0;j<n;j++)
		{
			map[i][j+1]=ls[j];
			if(map[i][j+1]>='a'&&map[i][j+1]<='e')
			{
				col[ls[j]]=0;
				cnt[ls[j]]++;
			}
			if(map[i][j+1]=='S') {sx=i;sy=j+1;}
		}
	}
}
void cal()
{
	int flag=1;//就是这里忘了赋值了。。。
	vector<NOTE> q;
	NOTE tmp;
	tmp.x=sx;tmp.y=sy;
	q.push_back(tmp);
	vis[sx][sy]=1;
	while(flag)
	{
		flag=0;
		for(int k=0;k<q.size();k++)
		{
			NOTE sta=q[k];
			for(int i=0;i<4;i++)
			{
				int tx=sta.x+d[i][0];
				int ty=sta.y+d[i][1];
				if(tx<=0||ty<=0||tx>m||ty>n) continue;
				if(map[tx][ty]=='G')
				{
					printf("YES\n");
					return;
				}
				if(map[tx][ty]=='.'&&!vis[tx][ty])
				{
					NOTE tp;
					tp.x=tx;tp.y=ty;
					q.push_back(tp);
					flag=1;
					vis[tx][ty]=1;
					continue;
				}
				if(map[tx][ty]=='X') continue;
				if(map[tx][ty]>='a'&&map[tx][ty]<='e'&&!vis[tx][ty])
				{
					col[map[tx][ty]]++;
					vis[tx][ty]=1;
					map[tx][ty]='.';
					NOTE tp;
					tp.x=tx;tp.y=ty;
					q.push_back(tp);
					flag=1;
					continue;
				}
				if(map[tx][ty]>='A'&&map[tx][ty]<='E'&&!vis[tx][ty])
				{
					if(col[map[tx][ty]+32]<cnt[map[tx][ty]+32]) continue;
					map[tx][ty]='.';
					vis[tx][ty]=1;
					NOTE tp;
					tp.x=tx;tp.y=ty;
					q.push_back(tp);
					flag=1;
					continue;
				}
			}
		}
	}
	printf("NO\n");
}
int main()
{
	while(scanf("%d%d",&m,&n)&&n&&m)
	{
		read();
		cal();
	}
	system("pause");
	return 0;
}

• 挺不错的搜索题. (2180) yygy 2013-02-25 18:24:09
  • 解题报告： (64) yygy 2013-02-26 08:47:22