Penguins(bfs 较难的题目)

一时失言乱红尘 2022-08-31 00:49 41阅读 0赞

#include <bits/stdc++.h>
    using namespace std;
    #define pii pair<int, int>
    #define ff first
    #define ss second
    const int N = 22;
    struct node
    { 
        int x1, y1, x2, y2; // 四个坐标
        vector<pii > A1;
        vector<pii > A2;
        string ans; // 记录答案
    };
    char g1[N][N], g2[N][N];
    bool vis[N][N][N][N];  // 记录是否走过
    
    int xd[4] = { 1, 0, 0, -1};  //下左右上
    int yd[4] = { 0, -1, 1, 0}; 
    
    
    char opt[6] = "DLRU";
    vector<char> v;
    void bfs()
    { 
        queue<node> q;
        vector<pii > A1, A2;
        A1.push_back({ 20, 20});  // 左边的起始位置
        A2.push_back({ 20, 1});  // 右边的起始位置
        q.push({ 20, 20, 20, 1, A1, A2, ""}); // 这里为什么要用A1 和 A2 去重复记录 坐标呢
        vis[20][20][20][1] = true; // 记录走过的位置
        while (q.size())
        { 
            node t = q.front();
            q.pop();
            int x1 = t.x1, y1 = t.y1, x2 = t.x2, y2 = t.y2;
            auto ans = t.ans; // auto自动类型推断
            auto A1 = t.A1; 
            auto A2 = t.A2; 
            if (x1 == 1 && y1 == 20 && x2 == 1 && y2 == 1) // 如果到达终点
            { 
                for (auto x : A1)
                { 
                    g1[x.ff][x.ss] = 'A';
                }
                for (auto x : A2)
                { 
                    g2[x.ff][x.ss] = 'A';
                }
                cout << ans.size() << endl;
                cout << ans << endl;
                for (int i = 1; i <= 20; ++i)
                { 
                    cout << (g1[i] + 1);
                    cout << " ";
                    cout << (g2[i] + 1);
                    cout << endl;
                }
                return;
            }
            auto AA1 = A1, AA2 = A2;
            string aans = ans;
            for (int i = 0; i < 4; ++i)
            { 
                A1 = AA1, A2 = AA2, ans = aans;
    
                // int xd[4] = {1, 0, 0, -1}; //下左右上
                // int yd[4] = {0, -1, 1, 0}; 
                // 这一步很妙，直接完成了镜像操作； 先操作然后在判断，如果合格，直接取，不合格，取原来的位置
                int xx1 = x1 + xd[i], yy1 = y1 + yd[i], xx2 = x2 + xd[i], yy2 = y2 - yd[i];
                if (xx1 < 1 || xx1 > 20 || g1[xx1][yy1] == '#')
                    xx1 = x1;
                if (yy1 < 1 || yy1 > 20 || g1[xx1][yy1] == '#')
                    yy1 = y1;
                if (xx2 < 1 || xx2 > 20 || g2[xx2][yy2] == '#')
                    xx2 = x2;
                if (yy2 < 1 || yy2 > 20 || g2[xx2][yy2] == '#')
                    yy2 = y2;
    
                if (vis[xx1][yy1][xx2][yy2]) // 如果已经到过了，直接跳过
                    continue;
                vis[xx1][yy1][xx2][yy2] = true; // 记录这个位置到过了
                A1.push_back({ xx1, yy1}); // 压入栈 中，继续搜下一个位置（对于左边来说）
                A2.push_back({ xx2, yy2}); // 压入栈 中，继续搜下一个位置（对于右边来说）
                q.push({ xx1, yy1, xx2, yy2, A1, A2, ans += opt[i]});
            }
        }
    }
    int main()
    { 
        for (int i = 1; i <= 20; ++i) // 整行读入操作，从第一个开始
        { 
            cin >> (g1[i] + 1); 
            cin >> (g2[i] + 1);
        }
        bfs(); // bfs遍历
        return 0;
    }