174. 推箱子（bfs+bfs）

比眉伴天荒 2021-11-10 15:50 409阅读 0赞

题目链接：[https://www.acwing.com/problem/content/description/176/][https_www.acwing.com_problem_content_description_176]  
这个题目大体思路还是比较简单的。  
首先，明确一点我们是要把物品移动到T的位置。  
如果物品当前在（x，y）。我向下移动一个位置，那么新的物品位置在（x + 1,y)。同时有人移动前的位置一定是在（x-1，y）处。这个位置才能把物品向下推。然后人新的位置就是（x，y）即物品之前的位置。

故，我们把人的位置，物品的位置打包成一个结构体。当我们把物品向四个方向移动时，同时bfs人到他应该到达的位置，如果人到不了那个位置，则此方向不能推。  
此份code有wa又limit。我真的是绝望了。这是个恶心题。日后，重新理一下思路，在写一下。

#include"stdio.h"
    #include"string.h"
    #include"string"
    #include"queue"
    #include"iostream"
    #include"algorithm"
    using namespace std;
    #define INF 10010101
    
    typedef pair<int,int> PII;
    typedef struct Node
    {
        int good_x,good_y;
        int p_x,p_y;
        PII step;
        string ans;
    } Node;
    
    const int dirx[4] = {-1,1,0,0};
    const int diry[4] = {0,0,-1,1};
    const char Good_dir[4] = {'N','S','W','E'};
    const char Peop_dir[4] = {'n','s','w','e'};
    
    PII dist[21][21][4];
    int vis[21][21][4],N,M;
    int used[21][21];
    Node start_node;
    char Graph[21][21];
    string min_ans,peo_min;
    int peo_step;
    PII min_step;
    
    int is_book(Node now)
    {
        if(now.good_x >= 1 && now.good_x <= N && now.good_y >= 1 && now.good_y <= M && (Graph[now.good_x][now.good_y] != '#' ))
            return 1;
        return 0;
    }
    
    int is_ok(Node now,Node T)
    {
        if(now.p_x >= 1 && now.p_x <= N && now.p_y >= 1 && now.p_y <= M && Graph[now.p_x][now.p_y] != '#' && (!(now.p_x == T.good_x && now.p_y == T.good_y)))
            return 1;
        return 0;
    }
    int bfs_man(Node Pre,Node T)
    {
        int vis[21][21];
        memset(vis,0,sizeof(vis));
        queue<Node> Q;
        Node t = T;
        t.step.first = 0;
        t.step.second = 0;
        t.ans = "";
        Q.push(t);
        vis[t.p_x][t.p_y] = 1;
        peo_step = 1001010;
        //printf("t :: %d %d\n",t.p_x,t.p_y);
        while(!Q.empty())
        {
            Node K = Q.front();
            Q.pop();
            // printf("K : P_x = %d P_y = %d\n",K.p_x,K.p_y);
            if(K.p_x == Pre.p_x && K.p_y == Pre.p_y)
            {
                peo_step = K.step.second;
                peo_min = K.ans;
                return 1;
            }
            for(int i = 0; i < 4; i ++)
            {
                Node pre = K;
                pre.p_x += dirx[i];
                pre.p_y += diry[i];
                // printf("pre :: %d %d %d vis = %d\n",pre.p_x,pre.p_y,is_ok(pre,T),vis[pre.p_x][pre.p_y]);
                //getchar();
                if(vis[pre.p_x][pre.p_y] == 0 && is_ok(pre,T) )
                {
    
                    pre.step.second ++;
                    pre.ans += Peop_dir[i];
                    vis[pre.p_x][pre.p_y] = 1;
                    Q.push(pre);
                }
            }
        }
        return 0;
    }
    
    int bfs_good()
    {
        queue<Node> Q;
        Q.push(start_node);
        int mark = 0;
        min_step.first = INF;
        while(!Q.empty())
        {
            Node T = Q.front();
            Q.pop();
            //printf("x = %d y = %d\n",T.good_x,T.good_y);
            if(Graph[T.good_x][T.good_y] == 'T')
            {
                if(T.step.first < min_step.first || (T.step.first == min_step.first && T.step.second < min_step.first))
                {
                    mark = 1;
                    min_step = T.step;
                    min_ans = T.ans;
                   // return 1;
                }
               // else if(T.step.first > min_step.first)
                    //return 1;
                continue;
            }
            for(int i = 0; i < 4; i ++)
            {
                Node next = T;
                next.good_x += dirx[i];
                next.good_y += diry[i];
                Node Pre = T;
                Pre.p_x = Pre.good_x - dirx[i];
                Pre.p_y = Pre.good_y - diry[i];
                //   printf("i = %d bfs_man = %d\n",i,bfs_man(Pre,T));
                if(used[next.p_x][next.p_y] == 0 && vis[next.good_x][next.good_y][i] == 0 && is_book(next) && bfs_man(Pre,T) == 1 )
                {
                    next.p_x = T.good_x;
                    next.p_y = T.good_y;
                    next.ans = T.ans + peo_min + Good_dir[i];
                    next.step.first = T.step.first + 1;
                    next.step.second = T.step.second + peo_step;
                    if(next.step.first >  dist[next.p_x][next.p_y][i].first || (next.step.first ==  dist[next.p_x][next.p_y][i].first && next.step.second >  dist[next.p_x][next.p_y][i].second))
                        continue;
                    dist[next.p_x][next.p_y][i] = next.step;
                  //  used[next.p_x][next.p_y] = 1;
                    vis[next.good_x][next.good_y][i] == 1;
                    Q.push(next);
                }
            }
        }
        return mark;
    }
    
    int main()
    {
        int cnt =  1;
        while(~scanf("%d%d",&N,&M))
        {
            if(N == 0 && M == 0) break;
            memset(vis,0,sizeof(vis));
            memset(used,0,sizeof(used));
            start_node.ans = "";
            min_step.first = 0;
            min_step.second = 0;
            start_node.step.first = 0;
            start_node.step.second = 0;
            start_node.p_x = 0;
            start_node.good_x = 0;
            for(int i = 0; i <= 20; i ++)
                for(int j = 0; j <= 20; j ++)
                    for(int k = 0; k < 4; k ++)
                        dist[i][j][k].first = INF,dist[i][j][k].second = INF;
            for(int i = 1; i <= N; i ++)
                scanf("%s",Graph[i] + 1);
            for(int i = 1; i <= N && (start_node.good_x == 0 || start_node.p_x == 0); i ++)
                for(int j = 1; j <= M && (start_node.good_x == 0 || start_node.p_x == 0); j ++)
                    if(Graph[i][j] == 'S')
                    {
                        start_node.p_x = i,start_node.p_y = j;
                        Graph[i][j] = '.';
                    }
                    else if(Graph[i][j] == 'B')
                    {
                        start_node.good_x = i,start_node.good_y = j;
                        Graph[i][j] = '.';
                    }
    
    
            printf("Maze #%d\n",cnt ++);
            //printf("x = %d y = %d\n",start_node.good_x,start_node.good_y);
            if(bfs_good() == 1)
                cout << min_ans << endl;
            else
                printf("Impossible.\n");
            printf("\n");
        }
    }

[https_www.acwing.com_problem_content_description_176]: https://www.acwing.com/problem/content/description/176/