题解：P13935 [蓝桥杯 2022 省 Java B] 回忆迷宫

V_star · 2026-01-24 15:26:02 · 题解

P13935 回忆迷宫思路：

1. 在模拟走过的路时：取最大最小坐标。

2. 将 \max 坐标 x，y 增加一， \min 相反。

3. 与走过路相邻变成墙。

4. 四个角点广搜，没撞墙没走过不越界变成 c。

5. 不是墙，路 c 变成墙。

6. 打印。

总结：

1. 全赋值成空。

2. 把走过的路赋值成墙。

3. 把中间漏掉的墙补上。

下面是代码示例:

#include <bits/stdc++.h>
using namespace std;
struct node {
    int x;
    int y;
};
queue<node> q;
char migong[505][505];//UDLR
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
bool vis[505][505] = {false};
int main() {
    int n, nowx = 205, nowy = 205, sx, sy, ex, ey;
    sx = 1e9;
    sy = 1e9;
    ex = 0;
    ey = 0;
    string s;
    cin >> n;
    cin >> s;
    migong[nowx][nowy] = ' ';
    sx = min(sx, nowx);
    ex = max(ex, nowx);
    sy = min(sy, nowy);
    ey = max(ey, nowy);
    for (int i = 0; i < n; i++) {
        if (s[i] == 'U') {
            migong[--nowx][nowy] = ' ';
            sx = min(sx, nowx);
            ex = max(ex, nowx);
            sy = min(sy, nowy);
            ey = max(ey, nowy);
        } else if (s[i] == 'D') {
            migong[++nowx][nowy] = ' ';
            sx = min(sx, nowx);
            ex = max(ex, nowx);
            sy = min(sy, nowy);
            ey = max(ey, nowy);
        } else if (s[i] == 'L') {
            migong[nowx][--nowy] = ' ';
            sx = min(sx, nowx);
            ex = max(ex, nowx);
            sy = min(sy, nowy);
            ey = max(ey, nowy);
        } else {
            migong[nowx][++nowy] = ' ';
            sx = min(sx, nowx);
            ex = max(ex, nowx);
            sy = min(sy, nowy);
            ey = max(ey, nowy);
        }
    }//走过路加坐标
    sx--;
    sy--;
    ex++;
    ey++;
    //cout << sx << ' ' << sy << ' ' << ex << ' ' << ey << endl;
    for (int i = sx; i <= ex; i++) {
        for (int j = sy; j <= ey; j++) {
            if (migong[i][j] == ' ') {
                if (i > sx && migong[i - 1][j] != ' ') {
                    migong[i - 1][j] = '*';
                }
                if (i < ex && migong[i + 1][j] != ' ') {
                    migong[i + 1][j] = '*';
                }
                if (j > sy && migong[i][j - 1] != ' ') {
                    migong[i][j - 1] = '*';
                }
                if (j < ey && migong[i][j + 1] != ' ') {
                    migong[i][j + 1] = '*';
                }
            }//路周围变成墙
        }
    }
    for (int i = sx; i <= ex; i++) {
        for (int j = sy; j <= ey; j++) {
            if (i == sx || i == ex || j == sy || j == ey) {
                if (migong[i][j] != '*') {
                    node a;
                    a.x = i;
                    a.y = j;
                    q.push(a);
                    vis[i][j] = true;
                    migong[i][j] = 'c';
                }
            }
        }
    }
    while (!q.empty()) {
        node temp = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            if (temp.x + dx[i] < sx || temp.x + dx[i] > ex || temp.y + dy[i] < sy || temp.y + dy[i] > ey || migong[temp.x + dx[i]][temp.y + dy[i]] == '*' || vis[temp.x + dx[i]][temp.y + dy[i]]) {
                continue;
            }//没撞墙没走过不越界
            migong[temp.x + dx[i]][temp.y + dy[i]] = 'c';
            node e;
            e.x = temp.x + dx[i];
            e.y = temp.y + dy[i];
            q.push(e);
            vis[temp.x + dx[i]][temp.y + dy[i]] = true;//入队
        }
    }
    for (int i = sx; i <= ex; i++) {
        for (int j = sy; j <= ey; j++) {
            if (migong[i][j] != ' ' && migong[i][j] != '*' && migong[i][j] != 'c') {
                migong[i][j] = '*';
            }
        }
    }//第六步
    for (int i = sx; i <= ex; i++) {
        for (int j = sy; j <= ey; j++) {
            if (migong[i][j] != 'c') {
                cout << migong[i][j];
            } else {
                cout << ' ';
            }
        }
        cout << endl;
    }//打印
    return 0;
}