题目描述

立体推箱子是一个风靡世界的小游戏。

游戏地图是一个N行M列的矩阵，每个位置可能是硬地（用”.”表示）、易碎地面（用”E”表示）、禁地（用”#”表示）、起点（用”X”表示）或终点（用”O”表示）。

你的任务是操作一个1×1×2的长方体。

这个长方体在地面上有两种放置形式，“立”在地面上（1×1的面接触地面）或者“躺”在地面上（1×2的面接触地面）。

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

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

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

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

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

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

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

输入格式
输入包含多组测试用例。

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

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

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

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

每个结果占一行。

数据范围
3≤N,M≤500

样例

输入样例：
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0
输出样例：
10

深搜

确定每一步的状态
立着：0；横躺：1；竖躺：2；坐标：(x,y)

宽搜框架不变，状态改变复杂

C++ 代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N=510;

int n,m;

struct State{
    int x,y,lie;
};

int dist[N][N][3];//从起始状态到现在的状态走了多少步
char g[N][N];
int d[3][4][3]={{{-2,0,2},{0,1,1},{1,0,2},{0,-2,1}},//第一行表示由状态0开始变化，上右下左
                {{-1,0,1},{0,2,0},{1,0,1},{0,-1,0}},
                {{-1,0,0},{0,1,2},{2,0,0},{0,-1,2}}};

bool check(int x,int y){
    //判断出界
    if(x<0||x>=n||y<0||y>=m)  return false;
    return g[x][y]!='#';
}
int bfs(State start,State end){
    memset(dist,-1,sizeof(dist));//表示每一个位置都还没有搜索
    dist[start.x][start.y][start.lie]=0;//初始距离为0
    queue<State>q;
    q.push(start);
    while(q.size()){
        State t=q.front();
        q.pop();
        //对t位置的状态进行转移扩展,往四个方向分别会变成什么
        for(int i=0;i<4;i++){
            State next;
            next={t.x+d[t.lie][i][0],t.y+d[t.lie][i][1],d[t.lie][i][2]};

            int x=next.x,y=next.y;
            if(!check(x,y))  continue;
            if(next.lie==0&&g[x][y]=='E')  continue;//是不是竖着站在脆弱的格子上
            if(next.lie==1&&!check(x,y+1))  continue;
            if(next.lie==2&&!check(x+1,y))  continue;
            if(dist[next.x][next.y][next.lie]==-1){
                dist[x][y][next.lie]=dist[t.x][t.y][t.lie]+1;
                q.push(next);
            }
        }
    }
    return dist[end.x][end.y][end.lie];
}
int main(){

    while(cin>>n>>m,n||m){
        for(int i=0;i<n;i++)  cin>>g[i];
        State start,end;//初始和结束
        start={-1};
        //寻找起点
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(g[i][j]=='X'&&start.x==-1){
                    if(g[i][j+1]=='X')  start={i,j,1};
                    else if(g[i+1][j]=='X')   start={i,j,2};
                    else start={i,j,0};
                }
                else if(g[i][j]=='O')  end={i,j,0};
            }
        }
        int res=bfs(start,end);
        if(res==-1)   cout<<"Impossible"<<endl;
        else cout<<res<<endl;
    }
    return 0;
}