2021牛客暑期多校訓練營2 I.Penguins

I.Penguins

題目大意：

在一個 20 ∗ 41 20*41 20∗41的網格裡有兩隻企鵝，一隻位于（20,20）點最終要到達（1,20）點，另一隻在（20,22）點最終要到達（1,22），兩隻企鵝在左右方向上做鏡面運動，在上下方向上同上同下，如果企鵝的下一步遇到障礙或是邊界，企鵝可以忽略這一步。

思路：

賽時調了好久沒有調出來啊。。😫補題又調了好久。。總而言之，思路很簡單，利用bfs将整個圖走一遍，将每一個點的上一個點進行儲存，最後按照字典序入隊即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<queue>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
const int N = 50;
char s[N][N];
int d[N][N][N][N];
int wha[N][N][N][N];

string ans;
struct node {
    int x1, y1, x2, y2;
    bool operator !=(node& x) {
        return x1 != x.x1 || x2 != x.x2 || y1 != x.y1 || y2 != x.y2;
    }
}hhh, pre[N][N][N][N];
int cnt = 0;
void inint() {
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= 20; j++)
            cin >> s[i][j];
        s[i][21] = ' ';
        for (int j = 22; j <= 41; j++)
            cin >> s[i][j];
    }
}
void bfs() {
    queue<node>q;
    hhh.x1 = 20, hhh.y1 = 20, hhh.x2 = 20, hhh.y2 = 22;
    q.push(hhh);
    memset(d, -1, sizeof d);
    d[20][20][20][22] = 0;
    while (q.size()) {
        hhh = q.front();
        q.pop();
        node t = hhh;
        int dis = d[hhh.x1][hhh.y1][hhh.x2][hhh.y2];
        int f1 = 0, f2 = 0;
        if (s[hhh.x1 + 1][hhh.y1] == '.' && hhh.x1 + 1 >= 1 && hhh.x1 + 1 <= 20 && hhh.y1 >= 1 && hhh.y1 <= 20)hhh.x1++;
        if (s[hhh.x2 + 1][hhh.y2] == '.' && hhh.x2 + 1 >= 1 && hhh.x2 + 1 <= 20 && hhh.y2 >= 22 && hhh.y2 <= 41)hhh.x2++;
        if (d[hhh.x1][hhh.y1][hhh.x2][hhh.y2] == -1)
        {
            q.push(hhh);
            wha[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = 0;//d
            d[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = dis + 1;
            pre[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = t;
        }

        hhh = t;
        if (s[hhh.x1][hhh.y1 - 1] == '.' && hhh.x1 >= 1 && hhh.x1 <= 20 && hhh.y1 - 1 >= 1 && hhh.y1 - 1 <= 20)hhh.y1--;
        if (s[hhh.x2][hhh.y2 + 1] == '.' && hhh.x2 >= 1 && hhh.x2 <= 20 && hhh.y2 + 1 >= 22 && hhh.y2 + 1 <= 41)hhh.y2++;
        if (d[hhh.x1][hhh.y1][hhh.x2][hhh.y2] == -1)
        {
            q.push(hhh);
            wha[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = 1;//l
            d[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = dis + 1;
            pre[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = t;

        }
        hhh = t;
        if (s[hhh.x1][hhh.y1 + 1] == '.' && hhh.x1 >= 1 && hhh.x1 <= 20 && hhh.y1 + 1 >= 1 && 1 + hhh.y1 <= 20)hhh.y1++;
        if (s[hhh.x2][hhh.y2 - 1] == '.' && hhh.x2 >= 1 && hhh.x2 <= 20 && hhh.y2 - 1 >= 22 && hhh.y2 - 1 <= 41)hhh.y2--;
        if (d[hhh.x1][hhh.y1][hhh.x2][hhh.y2] == -1)
        {
            q.push(hhh);
            wha[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = 2;//r
            d[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = dis + 1;
            pre[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = t;

        }
        hhh = t;
        if (s[hhh.x1 - 1][hhh.y1] == '.' && hhh.x1 - 1 >= 1 && hhh.x1 - 1 <= 20 && hhh.y1 >= 1 && hhh.y1 <= 20)hhh.x1--;
        if (s[hhh.x2 - 1][hhh.y2] == '.' && hhh.x2 - 1 >= 1 && hhh.x2 - 1 <= 20 && hhh.y2 >= 22 && hhh.y2 <= 41)hhh.x2--;
        if (d[hhh.x1][hhh.y1][hhh.x2][hhh.y2] == -1)
        {
            q.push(hhh);
            wha[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = 3;//u
            d[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = dis + 1;
            pre[hhh.x1][hhh.y1][hhh.x2][hhh.y2] = t;

        }
    }
}
int main() {
    inint();
    bfs();
    cout << d[1][20][1][22] << endl;
    node end = { 1,20,1,22 };
    node begin = { 20,20,20,22 };
    queue<char> p;
    char cc[4] = { 'D','L','R','U' };
    s[20][20] = s[20][22] = 'A';
    while (begin != end)
    {
        s[end.x1][end.y1] = s[end.x2][end.y2] = 'A';
        p.push(cc[wha[end.x1][end.y1][end.x2][end.y2]]);
        end = pre[end.x1][end.y1][end.x2][end.y2];
    }
    string ans = "";
    while (p.size())
    {
        ans = p.front() + ans;
        p.pop();
    }
    cout << ans << endl;
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= 20; j++)
            cout << s[i][j];
        cout << ' ';
        for (int j = 22; j <= 41; j++)
            cout << s[i][j];
        cout << endl;
    }

}