2021牛客暑期多校訓練營2.I Penguins BFS廣搜 簡單

火車上沒法寫，來補題了…

連結：https://ac.nowcoder.com/acm/contest/11253/I

題目描述

Lovely penguins is a tiny game in which the player controls two penguins.

The game holds in two 20 × 20 20×20 20×20 grids (the left one and the right one), and each has some blocked places.

We number the grid in x t h x^{th} xth row (starting from the up), y t h y^{th} yth column (starting from the left) ( x , y ) (x,y) (x,y)

The penguins move in four directions: up, down, left, right, exactly one step once. If its way is blocked, or it reaches the border, then this movement is omitted.

The player also moves the penguins in four directions, but the behavior of the two penguins is mirrored:

1. ​ L : left penguin moves to left, right penguin moves to right.
2. ​ R : left penguin moves to right, right penguin moves to left.
3. ​ U : both move upwards.
4. ​ D : both move downwards.

An operation can be omitted on one penguin but works on another.

The left penguin starts from ( 20 , 20 ) (20,20) (20,20) and wants to move to ( 1 , 20 ) (1,20) (1,20).The right penguin starts from ( 20 , 1 ) (20,1) (20,1) and wants to move to ( 1 , 1 ) (1,1) (1,1).If both penguin reach there destination, thay win the game.

Find out the shortest way to win the game.If there are many shortest ways to win, find the one with minimum lexicographical order(D<L<R<U).

Note: When one penguin reaches the destination and the other does not, the penguin that has reached the destination may still move out of the destination

輸入描述:

The input consists of 20 lines, each line contains 41 characters, describing the grids, separated by a space.
'.' means the grid is empty.
'#' means the grid is blocked.
           

輸出描述:

Output 22 lines.
The first line contains the least number of steps to win the game.
The second line contains a string consisting of 'L','R','U','D', describing a way to win.
There may be many ways to win, output the one with minimum lexicographical order.
Then output 20 lines, describing the track of the two penguins, mark the track with character 'A', and print as input.
           

思路

題目給定兩個并列的迷宮，左側以右下角為起點，右上角為終點，右側以左下角為起點，左上角為終點。

左邊上下移動，右側同樣上下移動；左側左右移動，右側與左側相反方向移動。一側被牆擋住不影響另外一側的移動。

輸出左側移動的的路徑長度、路徑、路徑矩陣。多路徑輸出字典序最小路徑。

就是一個簡單的BFS，使用一個四維數組 v i s [ x 1 ] [ y 1 ] [ x 2 ] [ y 2 ] vis[x1][y1][x2][y2] vis[x1][y1][x2][y2]記錄目前位置 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1, y_1),(x_2, y_2) (x1​,y1​),(x2​,y2​)的狀态，然後按照字典序周遊目前點四周位置，合法則繼續走，不合法跳過，走到終點就停止。

如果硬要說技巧的話，就是開結構體的時候記錄路徑？開四維數組記錄狀态？反正個人覺得沒什麼技巧，難點在于打字速度和大碼量的準确性。

AC CODE

#include <bits/stdc++.h>
#pragma GCC optimize("no-stack-protector")
#pragma comment(linker, "/STACK: 102400000, 102400000")
using namespace std;

#define nx1 next.x1
#define nx2 next.x2
#define ny1 next.y1
#define ny2 next.y2

//D L R U | D R L U
const int dy1[] = {0, -1, 1, 0}, dx1[] = {1, 0, 0, -1};
const int dy2[] = {0, 1, -1, 0}, dx2[] = {1, 0, 0, -1};
const char step[] = {'D', 'L', 'R', 'U'};
map<char, int> ser = {{'D', 0}, {'L', 1}, {'R', 2}, {'U', 3}};

int g1[21][21], g2[21][21];

bool vis[21][21][21][21];


struct st{
    int x1, y1, x2, y2;
    string ans;
    st(int x1, int y1, int x2, int y2, string s  = ""): x1(x1), x2(x2), y1(y1), y2(y2), ans(s) {};
    st add(int dx1, int dy1, int dx2, int dy2){
        st newst(x1 + dx1, y1 + dy1, x2 + dx2, y2 + dy2, ans);
        return newst;
    }
    st move(char nxt){
        return st{x1, y1, x2, y2, ans + nxt};
    }
};

string bfs(){
    queue<st> q;
    q.push(st(20, 20, 20, 1));
    vis[20][20][20][1] = true;
    while(!q.empty()){
        st now = q.front(); q.pop();
        if(now.x1 == 1 && now.y1 == 20 && now.x2 == 1 && now.y2 == 1) return now.ans;
        for(int i = 0; i < 4; i++){
            st next = now.add(dx1[i], dy1[i], dx2[i], dy2[i]);
            if(!g1[nx1][ny1] || nx1 < 1 || ny1 < 1 || nx1 > 20 || ny1 > 20) next = next.add(-dx1[i], -dy1[i], 0, 0);
            if(!g2[nx2][ny2] || nx2 < 1 || ny2 < 1 || nx2 > 20 || ny2 > 20) next = next.add(0, 0, -dx2[i], -dy2[i]);
            if(!vis[nx1][ny1][nx2][ny2]){
                next = next.move(step[i]);
                //cout << "Next_step: " << step[i] << endl;
                q.push(next);
                vis[nx1][ny1][nx2][ny2] = true;
            }
            //cout << "Next::data " << next.x1 << ' ' << next.y1 << ' ' << next.x2 << ' ' << next.y2 << ' '  << next.ans << endl;
            //q.push(next);
        }
    }
    //return "";
}

void path(string ans){
    int x1 = 20, y1 = 20, x2 = 20, y2 = 1;
    g1[x1][y1] = -1, g2[x2][y2] = -1;
    for(auto cur : ans){
        int now = ser[cur];
        int xx1 = x1 + dx1[now], yy1 = y1 + dy1[now], xx2 = x2 + dx2[now], yy2 = y2 + dy2[now];
        if(!g1[xx1][yy1]) xx1 -= dx1[now], yy1 -= dy1[now];
        if(!g2[xx2][yy2]) xx2 -= dx2[now], yy2 -= dy2[now];
        x1 = xx1, x2 = xx2, y1 = yy1, y2 = yy2;
        g1[x1][y1] = -1, g2[x2][y2] = -1;
    }
}

void print(){
    for(int i = 1; i <= 20; i++){
        for(int j = 1; j <= 20; j++){
            if(g1[i][j] == 1) putchar('.');
            else if(g1[i][j] == 0) putchar('#');
            else if(g1[i][j] == -1) putchar('A');
        }
        putchar(' ');
        for(int j = 1; j <= 20; j++){
            if(g2[i][j] == 1) putchar('.');
            else if(g2[i][j] == 0) putchar('#');
            else if(g2[i][j] == -1) putchar('A');
        }
        putchar('\n');
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    for(int i = 1; i <= 20; i++){
        string tmp; getline(cin, tmp);
        for(int j = 1; j <= 20; j++) g1[i][j] = (tmp[j - 1] == '.' ? 1 : 0);
        for(int j = 1; j <= 20; j++) g2[i][j] = (tmp[j + 20] == '.' ? 1 : 0);
    }
    string ans = bfs();
    cout << ans.size() << endl << ans << endl;

    path(ans);

    print();
    /*
    for(int i = 1; i <= 20; i++){
        for(int j = 1; j <= 20; j++) cout << g1[i][j] << ' ';
        cout << endl;
    }

    for(int i = 1; i <= 20; i++){
        for(int j = 1; j <= 20; j++) cout << g2[i][j] << ' ';
        cout << endl;
    }*/

    return 0;
}