> #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;
> }

• 解题报告： (64) yygy 2013-02-26 08:47:22