poj3322_code.cpp

问题:移动矩形方块

#include<stdio.h>
#include<iostream>
using namespace std;
char map[503][503];
bool used[503][503][4];
struct node
{
	int r,c,s;
};
node stk[2000000];
int n,m;
node target;
node start;
bool change(node in,int state,node &out)
{
	if(in.s==3)
	{
		if(state==1)
		{
			out.r=in.r;out.c=in.c+1;out.s=1;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r][out.c+1]=='#')return false;
			return true;
		}
		if(state==2)
		{
			out.r=in.r+1;out.c=in.c;out.s=2;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r+1][out.c]=='#')return false;
			return true;
		}
		if(state==3)
		{
			out.r=in.r;out.c=in.c-2;out.s=1;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r][out.c+1]=='#')return false;
			return true;
		}
		if(state==4)
		{
			out.r=in.r-2;out.c=in.c;out.s=2;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r+1][out.c]=='#')return false;
			return true;
		}		
	}
	if(in.s==1)
	{
		if(state==1)
		{
			out.r=in.r;out.c=in.c+2;out.s=3;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r][out.c]=='E')return false;
			return true;
		}
		if(state==2)
		{
			out.r=in.r+1;out.c=in.c;out.s=1;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r][out.c+1]=='#')return false;
			return true;
		}
		if(state==3)
		{
			out.r=in.r;out.c=in.c-1;out.s=3;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r][out.c]=='E')return false;
			return true;
		}
		if(state==4)
		{
			out.r=in.r-1;out.c=in.c;out.s=1;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r][out.c+1]=='#')return false;
			return true;
		}
	}
	if(in.s==2)
	{
		if(state==1)
		{
			out.r=in.r;out.c=in.c+1;out.s=2;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r+1][out.c]=='#')return false;
			return true;
		}
		if(state==2)
		{
			out.r=in.r+2;out.c=in.c;out.s=3;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r][out.c]=='E')return false;
			return true;
		}
		if(state==3)
		{
			out.r=in.r;out.c=in.c-1;out.s=2;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r+1][out.c]=='#')return false;
			return true;
		}
		if(state==4)
		{
			out.r=in.r-1;out.c=in.c;out.s=3;
			if(out.r<=0||out.r>=n||out.c<=0||out.c>=m)return false;
			if(used[out.r][out.c][out.s])return false;
			if(map[out.r][out.c]=='#'||map[out.r][out.c]=='E')return false;
			return true;
		}
	}
}
void bfs()
{
	bool cyes;
	int i,j,step=0;
	node tmp;
	stk[0]=start;
	int trear,head=0,rear=1;
	while(head<rear)
	{
		step++;
		trear=rear;
		for(i=head;i<rear;i++)
		{
			for(j=1;j<=4;j++)
			{
				cyes=change(stk[i],j,tmp);
				if(cyes)
				{
					if(tmp.r==target.r&&tmp.c==target.c&&tmp.s==target.s)
					{
						printf("%d\n",step);return;
					}
					stk[trear++]=tmp;
					used[tmp.r][tmp.c][tmp.s]=true;;
				}
			}
		}
		head=rear;
		rear=trear;
	}
	printf("Impossible\n");
	return;
}
int main()
{
	while(scanf("%d%d",&n,&m),n&&m)
	{
		int i,j,cnt=0;
		char temp[1000];
		memset(used,0,sizeof(used));
		for(i=0;i<n;i++)
		{
			scanf("%s",temp);
			for(j=0;j<m;j++)
			{
				map[i][j]=temp[j];
				if(temp[j]=='X')
				{
					cnt++;
					start.r=i;start.c=j;start.s=3;
				}
				if(temp[j]=='O')
				{
					target.r=i;target.c=j;target.s=3;
				}
			}
		}
		if(cnt==2)
		{
			if(map[start.r-1][start.c]=='X')
			{
				start.r--;start.s=2;
			}
			else
			{
				start.c--;start.s=1;
			}
		}
//		printf("%d %d %d %d %d %d\n",start.r,start.c,start.s,target.r,target.c,target.s);
		bfs();
	}
	return 0;
}