【YBT高效进阶】1基础算法/5广度优先搜索/3立体推箱子

内存限制：256 MiB
时间限制：1000 ms
标准输入输出
题目类型：传统
评测方式：文本比较

题目描述

有一个 N*M 的矩阵，每个位置可能是硬地（用 . 表示），易碎地面（用 E 表示），禁地（用 # 表示），起点（用 X 表示），终点（用 O 表示）。

你的任务是操作一个 112 的长方体。

这个长方体在地面上有两种放置方式，" 立 " 在地面上（ 11的面接触地面）或者 " 躺 " 在地面上（ 12的面接触地面）。

在每一步操作中，可以按上下左右的四个键之一。

按下按键之后，长方体向对应的方向沿着棱滚动 90度 。

任意时刻，长方体不能有任何部位接触禁地，并且不能立在易碎地面上。

字符 X 标识长方体的起始位置，地图上可能有一个 X 或者两个相邻的 X。

地图上唯一的一个字符 O 标识目标位置。

求把长方体移动到目标位置（即立在 O 上）所需要的最少步数。

在移动过程中，X 和 O 的表示位置都可以看作是硬地被利用。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包括两个整数 n 和 m。

接下来 n 行用来描述地图，每行包括 m 个字符，每个字符表示一块地图的具体状态。

当输入用例 n=0,m=0 时，表示输入终止，且该用例无需考虑。

输出格式

每个用例输出一个整数表示所需的最少步数，如果无解则输出 Impossible。

每个结果占一行。

样例

样例输入

7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0

样例输出

10

数据范围与提示

对于 100% 的数据，有3<=n,m<=500 。

思路

用3个数保存长方体的状态。
2个数表示坐标。
1个数
0：立着
1：横着，(x,y)为右边点的位置
2：竖着，(x,y)为下面点的位置

代码

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;
struct jgt
{
	int x,y,t,s;
};
jgt b[750010];
char a[510][510];
bool d[510][510][3];
int n,m,sx,sy,st,zx,zy,way[3][4][3]={{{-1,0,2},{2,0,2},{0,-1,1},{0,2,1}},{{-1,0,1},{1,0,1},{0,-2,0},{0,1,0}},{{-2,0,0},{1,0,0},{0,-1,2},{0,1,2}}};
void input()
{
	int i,j;
	memset(d,true,sizeof(d));
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			cin>>a[i][j];
	for(i=1;i<=n;i++)//找起点
		for(j=1;j<=m;j++)
			if(a[i][j]=='X')
			{
				if(a[i-1][j]=='X')
				{
					sx=i;
					sy=j;
					st=2;
				}
				else
					if(a[i+1][j]=='X')
					{
						sx=i+1;
						sy=j;
						st=2;
					}
					else
						if(a[i][j-1]=='X')
						{
							sx=i;
							sy=j;
							st=1;
						}
						else
							if(a[i][j+1]=='X')
							{
								sx=i;
								sy=j+1;
								st=1;
							}
							else
							{
								sx=i;
								sy=j;
								st=0;
							}
				return;
			}
	return;
}
void BFS()
{
	int i,l,r,dx,dy,dt;
	d[sx][sy][st]=0;
	b[1].x=sx;
	b[1].y=sy;
	b[1].s=0;
	b[1].t=st;
	for(l=r=1;l<=r;l++)
		for(i=0;i<4;i++)//扩展
		{
			dx=b[l].x+way[b[l].t][i][0];//算出状态
			dy=b[l].y+way[b[l].t][i][1];
			dt=way[b[l].t][i][2];
			if(a[dx][dy]=='O'&&dt==0)//到达终点
			{
				printf("%d\n",b[l].s+1);
				return;
			}
			if((!(a[dx][dy]=='#'||(dt==0&&(dx<1||dx>n||dy<1||dy>m||a[dx][dy]=='E'))||(dt==1&&(dx<1||dx>n||dy<2||dy>m||a[dx][dy-1]=='#'))||(dt==2&&(dx<2||dx>n||dy<1||dy>m||a[dx-1][dy]=='#'))))&&d[dx][dy][dt])//条件
			{
				r++;
				b[r].x=dx;
				b[r].y=dy;
				b[r].t=dt;
				b[r].s=b[l].s+1;
				d[dx][dy][dt]=0;
			}
		}
	printf("Impossible\n");
	return;
}
int main()
{
	for(scanf("%d%d",&n,&m);n||m;scanf("%d%d",&n,&m))
	{
		input();
		BFS();
	}
	return 0;
}