2157.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#define NMAX 35
#define INF 1000000001
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
const int kn=5;
#define upper(x) (x>='A'&&x<='E')
#define lower(x) (x>='a'&&x<='e')

typedef struct 
{
	int y;
	int x;
}data;
int m[NMAX][NMAX];
bool f[NMAX][NMAX];
char a[NMAX][NMAX];
data que[NMAX*NMAX*1000+1];
int front,end;
int open[5];

int xp[4]={0,1,0,-1},yp[4]={-1,0,1,0};
int min;
int stx,sty,edx,edy;
int M,N;
data stp,edp;
int enque(data t)
{
	que[end]=t;
	end++;
	return 1;
}
int deque(data &t)
{
	if(front==end)
	{
	
		return 0;
	}
	t=que[front];
	front++;
	return 1;
}
void input()
{
	memset(open,0,sizeof(open));
	int i,j;
	for(i=1;i<=M;i++)
	{
		gets(a[i]+1);
		for(j=1;j<=N;j++)
		{
			if(a[i][j]=='.')
				continue;
			if(a[i][j]=='S')
			{
				stp.x=j;
				stp.y=i;
			}
			else if(a[i][j]=='G')
			{
				edp.x=j;edp.y=i;
			}
			else if(a[i][j]>='a'&&a[i][j]<='e')
			{
				open[a[i][j]-'a']++;
			}
		}
	}

}

int search()
{
	memset(f,0,sizeof(f));
	front=end=0;
	enque(stp);
	data cp,np;
	f[stp.y][stp.x]=1;
	int p;
	while(deque(cp))
	{
		for(p=0;p<4;p++)
		{
			np.x=cp.x+xp[p];
			np.y=cp.y+yp[p];
			if(np.x>N||np.y>M||np.x<1||np.y<1||upper(a[np.y][np.x])||a[np.y][np.x]=='X'||f[np.y][np.x])
				continue;
			if(lower(a[np.y][np.x]))
			{
				open[a[np.y][np.x]-'a']--;
				a[np.y][np.x]='.';
			}
			if(np.x==edp.x&&np.y==edp.y)
				return 1;
			f[np.y][np.x]=1;
			enque(np);
		}
	}
	return 0;
}
int openkey()
{
	memset(f,0,sizeof(f));
	bool flag=0;
	front=end=0;
	enque(stp);
	data cp,np;
	f[stp.y][stp.x]=1;
	int p;
	while(deque(cp))
	{
		for(p=0;p<4;p++)
		{
			np.x=cp.x+xp[p];
			np.y=cp.y+yp[p];
			if(np.x>N||np.y>M||np.x<1||np.y<1||f[np.y][np.x]||a[np.y][np.x]=='X')
				continue;
			if(upper(a[np.y][np.x]))
			{
				if(open[a[np.y][np.x]-'A']==0)
				{
					a[np.y][np.x]='.';
					flag=1;
					f[stp.y][stp.x]=1;
					enque(np);
				}
				else
				{
					continue;
				}
			}
			f[np.y][np.x]=1;
			enque(np);
		}
	}
	return flag;
}
int solve()
{
	
	while(1)
	{
		memset(f,0,sizeof(f));
		if(search())
			return 1;
		if(!openkey())
			return 0;

	}
}
main()
{
#if _DEBUG 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	while(1)
	{
		scanf("%d%d\n",&M,&N);
		if(!M)
			break;
		input();
		if(solve())
			printf("YES\n");
		else
			printf("NO\n");
	}
#if _DEBUG 
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}