172. 立体推箱子（bfs）

怼烎@ 2021-11-09 11:18 280阅读 0赞

题目链接:[https://www.acwing.com/problem/content/174/][https_www.acwing.com_problem_content_174]

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

游戏地图是一个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

输出样例：

分析：题目没有最恶心，只有更恶心。  
我真的就想骂一句mmp。为什么我字符串输入不行（本地不行）。感觉cb出毛病了。烦  
这个题无非就是迷宫问题了。  
但是需要注意，因为它是一个小的长方体的移动，并且有立 躺 两种状态。  
所以我们需要区别立 躺 两种状态，并且横躺和竖躺也是两种不同的状态。  
所以对于一个状态而言，我们可以用三元组\{x,y,lie\} 来保存。  
然后，就当前状态向上下左右移动，对这个三元组的改变是什么，我们可以用数组来保存。

#include"stdio.h"
    #include"string.h"
    #include"map"
    #include"queue"
    #include"algorithm"
    using namespace std;
    
    typedef struct Node1
    {
        int state,x,y,step;
        Node1(int a,int b,int c,int d)
        {
            state = a;
            x = b;
            y = c;
            step = d;
        }
        Node1()
        {
    
        }
    } Node;
    //数组next_x表示x的移动后的改变情况。x[2][2]表示从竖躺状态向下移动，x的改变
    const int next_x[3][4] = {
       {-2,0,1,0},{-1,0,1,0},{-1,0,2,0}};
    const int next_y[3][4] = {
       {0,1,0,-2},{0,2,0,-1},{0,1,0,-1}};
    const int next_lie[3][4] = {
       {2,1,2,1},{1,0,1,0},{0,2,0,2}};
    
    int N,M;
    int Graph[510][510];
    Node node,end_node,start_node;
    int vis[3][510][510];
    
    int check(int x,int y,int lie)
    {
        if(x >= 1 && x <= N && y >= 1 && y <= M)
        {
            if(Graph[x][y] == '#')
                return 0;
            if(lie == 0 && Graph[x][y] == 'E')
                return 0;
            if(lie == 1 && Graph[x][y + 1] == '#')
                return 0;
            if(lie == 2 && Graph[x + 1][y] == '#')
                return 0;
            return 1;
        }
        return 0;
    }
    
    int equal_node(Node T)
    {
        if(T.state == 0 && T.x == end_node.x && T.y == end_node.y)
            return 1;
        return 0;
    }
    
    int Check(Node T)
    {
        int x = T.x,y = T.y,lie = T.state;
        if(check(x,y,lie) == 0)
            return 0;
        if(vis[lie][x][y] == 1)
            return 0;
        vis[lie][x][y] = 1;
        return 1;
    }
    
    int bfs()
    {
        queue<Node> Q;
        Q.push(start_node);
        Node T = start_node;
        vis[T.state][T.x][T.y] = 1;
       // printf("%d %d %d \n",T.state,T.x,T.y);
        while(!Q.empty())
        {
            Node T = Q.front();
            Q.pop();
            if(equal_node(T) == 1)
                return T.step;
    
            int main1 = T.state;
            for(int i = 0; i < 4; i ++)
            {
                Node T1 = T;
                T1.state = next_lie[main1][i];
                T1.x = T.x + next_x[main1][i];
                T1.y = T.y + next_y[main1][i];
                T1.step ++;
                if(Check(T1) == 1)
                {
                    Q.push(T1);
                    //printf("lie = %d x = %d y = %d\n",T1.state,T1.x,T1.y);
                }
            }
        }
        return -1;
    }
    
    int main()
    {
        while(~scanf("%d%d",&N,&M))
        {
            if(N == 0 && M == 0) return 0;
            memset(vis,0,sizeof(vis));
            getchar();
            start_node.state = -1;
            start_node.step = 0;
            for(int i = 1; i <= N; i ++)
            {
                for(int j = 1; j <= M; j ++)
                {
                    scanf("%c",&Graph[i][j]);
                    if(Graph[i][j] == 'O')
                    {
                        end_node.state = 0;
                        end_node.x = i;
                        end_node.y = j;
                    }
                }
                getchar();
            }
            int mark = 0;
            for(int i = 1; i <= N; i ++)
            {
                for(int j = 1; j <= M; j ++)
                {
                    // printf("j = %d M = %d %c \n",j,M,Graph[i][j]);
                    //printf("%c",Graph[i][j]);
                    if(Graph[i][j] == 'X')
                    {
                        if(Graph[i][j + 1] == 'X')
                        {
                            start_node.state = 1;
                            start_node.x = i;
                            start_node.y = j;
                        }
                        else if(Graph[i + 1][j] == 'X')
                        {
                            start_node.state = 2;
                            start_node.x = i;
                            start_node.y = j;
                        }
                        else
                        {
                            start_node.state = 0;
                            start_node.x = i;
                            start_node.y = j;
                        }
                        mark = 1;
                        break;
                    }
                }
                if(mark == 1)
                    break;
            }
            int step = bfs();
            if(step == -1)
                printf("Impossible\n");
            else
                printf("%d\n",step);
        }
    }

[https_www.acwing.com_problem_content_174]: https://www.acwing.com/problem/content/174/