maze1.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: maze1
LANG: C++
*/
#include <iostream>
using namespace std;

bool map[39][101][4];

int W,H;
bool hash[39][101];
int statex[10000],statey[10000],fr=0,e=-1,step=0;

int main()
{
	freopen("maze1.in","r",stdin);
	freopen("maze1.out","w",stdout);
	scanf("%d%d\n",&W,&H);
	char ch;
	scanf("%c",&ch);
	for(int a=1;a<=W;a++)
	{
		scanf("%c",&ch);
		map[a][1][1]=true;
		if(ch==' ')
		{statex[++e]=a;statey[e]=1;}
		scanf("%c",&ch);
	}
	scanf("%c",&ch);
	
	for(int a=1;a<=H;a++)
	{
		map[1][a][0]=true;
		scanf("%c",&ch);
		if(ch==' ')
		{statex[++e]=1;statey[e]=a;}
		for(int b=1;b<=W-1;b++)
		{
			scanf("%c",&ch);
			scanf("%c",&ch);
			if(ch=='|')
			{map[b][a][2]=true;map[b+1][a][0]=true;}
		}
		scanf("%c",&ch);
		scanf("%c",&ch);
		map[W][a][2]=true;
		if(ch==' ')
		{statex[++e]=W;statey[e]=a;}
		scanf("%c",&ch);
		if(a==H) break;
		scanf("%c",&ch);
		for(int b=1;b<=W;b++)
		{
			scanf("%c",&ch);
			if(ch=='-')
			{map[b][a][3]=true;map[b][a+1][1]=true;}
			scanf("%c",&ch);
		}
		scanf("%c",&ch);
	}
	scanf("%c",&ch);
	for(int a=1;a<=W;a++)
	{
		map[a][H][3]=true;
		scanf("%c",&ch);
		if(ch==' ')
		{statex[++e]=a;statey[e]=H;}
		scanf("%c",&ch);
	}
	int te;
	hash[statex[0]][statey[0]]=true;
	hash[statex[1]][statey[1]]=true;
	while(e>=fr)
	{
		te=e;
		step++;
		for(int a=fr;a<=te;a++)
		{
			if(statex[a]>1)
				if(!hash[statex[a]-1][statey[a]]&&!map[statex[a]][statey[a]][0])
				{
					hash[statex[a]-1][statey[a]]=true;
					statex[++e]=statex[a]-1;statey[e]=statey[a];
				}
			if(statex[a]<W)
				if(!hash[statex[a]+1][statey[a]]&&!map[statex[a]][statey[a]][2])
				{
					hash[statex[a]+1][statey[a]]=true;
					statex[++e]=statex[a]+1;statey[e]=statey[a];
				}
			if(statey[a]>1)
				if(!hash[statex[a]][statey[a]-1]&&!map[statex[a]][statey[a]][1])
				{
					hash[statex[a]][statey[a]-1]=true;
					statex[++e]=statex[a];statey[e]=statey[a]-1;
				}
			if(statey[a]<H)
				if(!hash[statex[a]][statey[a]+1]&&!map[statex[a]][statey[a]][3])
				{
					hash[statex[a]][statey[a]+1]=true;
					statex[++e]=statex[a];statey[e]=statey[a]+1;
				}
		}
		fr=te+1;
	}
	printf("%d\n",step);
	return 0;
}