172. 立体推箱子
立体推箱子是一个风靡世界的小游戏。
游戏地图是一个 NN 行 MM 列的矩阵，每个位置可能是硬地（用 . 表示）、易碎地面（用 E 表示）、禁地（用 # 表示）、起点（用 X 表示）或终点（用 O 表示）。
你的任务是操作一个 1×1×21×1×2 的长方体。
这个长方体在地面上有两种放置形式，“立”在地面上（1×11×1 的面接触地面）或者“躺”在地面上（1×21×2 的面接触地面）。
在每一步操作中，可以按上下左右四个键之一。
按下按键之后，长方体向对应的方向沿着棱滚动 9090 度。
任意时刻，长方体不能有任何部位接触禁地，并且不能立在易碎地面上。
字符 X 标识长方体的起始位置，地图上可能有一个 X 或者两个相邻的 X。
地图上唯一的一个字符 O 标识目标位置。
求把长方体移动到目标位置（即立在 O 上）所需要的最少步数。
在移动过程中，X 和 O 标识的位置都可以看作是硬地被利用。
输入格式
输入包含多组测试用例。
对于每个测试用例，第一行包括两个整数 NN 和 MM。
接下来 NN 行用来描述地图，每行包括 MM 个字符，每个字符表示一块地面的具体状态。
当输入用例 N=0，M=0N=0，M=0 时，表示输入终止，且该用例无需考虑。
输出格式
每个用例输出一个整数表示所需的最少步数，如果无解则输出 Impossible。
每个结果占一行。
数据范围
3≤N,M≤5003≤N,M≤500
输入样例：
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0
输出样例：
10
'''
思路：
bfs 记录每个位置的坐标和三种状态作为当前状态，然后进行状态扩展
横躺着和竖躺着的时候只记录最左边或者最上面的点
状态转移时，躺着的状态需要两个点同时落在地面上才满足条件
'''
def sol():
n,m=[int(x) for x in r.split()]
g=['']*n
for i in range(n):
g[i]=input()
start=[-1,-1,-1]
end=[]
# 0 立着 1横躺着 2 竖躺着
for i in range(n):
for j in range(m):
if g[i][j]=='X' and start[0]==-1:
start=[i,j,0]
if g[i+1][j]=='X':start[2]=2
elif g[i][j+1]=='X': start[2]=1
elif g[i][j]=='O': end=[i,j,0]
# 能够到达某个点的最短距离
dist = [[[-1]*3 for i in range(m)] for j in range(n)]
def check(x,y):
if x<0 or x >=n or y<0 or y>=m:
return False
return g[x][y] != '#'
def bfs(start,end):
dist[start[0]][start[1]][start[2]]=0
# 数组模拟队列
q = [0]*(n*m*3)
tt,ff=0,0
q[0]=start
# 状态转移
# 3种状态在向上右下左四个方向反转之后的坐标和状态
d = [
[[-2,0,2],[0,1,1],[1,0,2],[0,-2,1]], # 立着
[[-1,0,1],[0,2,0],[1,0,1],[0,-1,0]], # 横躺
[[-1,0,0],[0,1,2],[2,0,0],[0,-1,2]], # 竖躺
]
while tt<=ff:
i,j,lie=q[tt]
tt+=1
for k in range(4):
nex = [i+d[lie][k][0],j+d[lie][k][1],d[lie][k][2]]
x,y,lie2 = nex
if not check(x,y): continue
if lie2==0 and g[x][y]=='E': continue
if lie2==1 and not check(x,y+1): continue
if lie2==2 and not check(x+1,y): continue
if dist[x][y][lie2] !=-1 : continue
dist[x][y][lie2]=dist[i][j][lie] + 1
ff+=1
q[ff]=nex
return dist[end[0]][end[1]][end[2]]
res = bfs(start,end)
print('Impossible' if res==-1 else res)
r=input()
while r!= '0 0':
sol()
r=input()