2802269_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <list>

using namespace std;

int m, n;
char map[21][21];
int num[6];
int get[6];
int sti, stj;
int edi, edj;
struct node
{
	int i, j;
};
int visited[21][21];

list <node> que;
list <node> ::iterator iter;

int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};

int valid(int a,int b)
{
	if(a<0||a>=m||b<0||b>=n)
		return 0;
	return 1;
}

void floodfill(int a,int b)
{
	int i;
	int ta, tb;

	visited[a][b] = 1;
	for(i = 0; i < 4; i++)
	{
		ta = a+mov[i][0];
		tb = b+mov[i][1];
		if(valid(ta,tb)&&!visited[ta][tb]&&map[ta][tb]!='X')
		{
			if(map[ta][tb]=='.')
				floodfill(ta,tb);
			else
				if(map[ta][tb]<='e'&&map[ta][tb]>='a')
				{
					get[map[ta][tb]-'a']++;
					map[ta][tb] = '.';
					floodfill(ta,tb);
				}
				else
					if(num[map[ta][tb]-'A']==get[map[ta][tb]-'A'])
					{
						map[ta][tb] = '.';
						floodfill(ta,tb);
					}
					else
					{
						node t;

						t.i = ta;t.j = tb;
						que.push_back(t);
					}
		}
	}
}

void solve()
{
	bool flag;
	int a, b;

	floodfill(sti,stj);
	flag = true;
	while(flag&&!que.empty())
	{
		flag = false;
		for(iter = que.begin(); iter != que.end(); ++iter)
		{
			a = (*iter).i;
			b = (*iter).j;
			if(num[map[a][b]-'A']==get[map[a][b]-'A'])
			{
				flag = true;
				map[a][b] = '.';
				que.erase(iter);
				floodfill(a,b);
				break;
			}
		}
	}
}

int main()
{
	int i, j;

	while(scanf("%d%d",&m,&n)==2,m)
	{
		que.clear();
		memset(num,0,sizeof(num));
		for(i = 0; i < m; i++)
			scanf("%s",map[i]);
		for(i = 0; i < m; i++)
			for(j = 0; j < m; j++)
			{
				if(map[i][j]=='S')
				{
					map[i][j] = '.';
					sti = i;
					stj = j;
				}
				if(map[i][j]=='G')
				{
					map[i][j] = '.';
					edi = i;
					edj = j;
				}
				if(map[i][j]<='e'&&map[i][j]>='a')
					num[map[i][j]-'a']++;
			}
			memset(visited,0,sizeof(visited));
			memset(get,0,sizeof(get));
			solve();
			if(visited[edi][edj])
				puts("YES");
			else
				puts("NO");
	}
	return 0;
}