返回题解分享
讨论 / 题解分享/ 帖子详情

回忆迷宫(编程题) - 题解

using namespace std;

#define maxn 105

int tu[maxn][maxn]; // tu[i][j]为0表示未定,为1表示为迷宫内空地,为2表示为墙,为3表示迷宫外空地 
unordered_map<char, int> dire;
int n, step[maxn];
int initx, inity; // 初始位置的横纵坐标,比如样例中的initx=6,inity=6 
int hangshu, lieshu; // 整个图的行数和列数,比如样例中的hangshu为7,lieshu为7 
int mymove[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool vis[maxn][maxn]; 

void getinfor() {
    int x = 0, y = 0;
    initx = max(initx, x + 2);
    inity = max(inity, y + 2);
    for (int i = 1; i <= n; i++) {
        switch (step[i]) {
            case 1:
                x++;
                initx = max(initx, x + 2);
                break;
            case 2:
                x--; 
                break;
            case 3:
                y++;
                inity = max(inity, y + 2);
                break;
            case 4:
                y--;
                break;
        }
    }
}

void dfs(int x, int y) {
    for (int i = 1; i <= n; i++) {
        tu[x][y] = 1;
        hangshu = max(hangshu, x);
        lieshu = max(lieshu, y); 
        switch (step[i]) {
            case 1:
                x--;
                break;
            case 2:
                x++; 
                break;
            case 3:
                y--;
                break;
            case 4:
                y++;
                break;
        }
    }
    tu[x][y] = 1;
    hangshu = max(hangshu, x);
    lieshu = max(lieshu, y); 
    hangshu++;
    lieshu++; // 因为右边和上边要有墙 
}

void dfs1(int x, int y) { // 这是为了将围墙围住的部分置为围墙
    int nextx, nexty;
    for (int i = 0; i < 4; i++) {
        nextx = x + mymove[i][0];
        nexty = y + mymove[i][1];
        if (tu[nextx][nexty] == 0 && 1 <= nextx && nextx <= hangshu && 1 <= nexty && nexty <= lieshu) {
            tu[nextx][nexty] = 3;
            dfs1(nextx, nexty);
        }
    }
}

int main() {
    scanf("%d", &n);
    dire['U'] = 1;
    dire['D'] = 2;
    dire['L'] = 3;
    dire['R'] = 4;
    string str;
    cin >> str;
    for (int i = 1; i <= n; i++) {
        step[i] = dire[str[i - 1]];
    }
    memset(tu, 0, sizeof(tu)); 
    getinfor(); // 根据step[]获取一些信息 
    dfs(initx, inity);
    for (int i = 1; i <= hangshu; i++) {
        for (int j = 1; j <= lieshu; j++) {
            vis[i][j] = 1; 
            if (tu[i][j] == 0) { // 这个元素未定 
                if (tu[i - 1][j] == 1 || tu[i + 1][j] == 1 || tu[i][j - 1] == 1 || tu[i][j + 1] == 1) {
                    tu[i][j] = 2; // 设置为围墙 
                }
            }
        }
    }
    for (int i = 1; i <= hangshu; i++) {
        if (i == 1 || i == hangshu) {
            for (int j = 1; j <= lieshu; j++) {
                if (tu[i][j] == 0) {
                    tu[i][j] = 3; // 置为迷宫外空地 
                    dfs1(i, j);
                }
            }
        } else {
            if (tu[i][1] == 0) {
                tu[i][1] = 3;
                dfs1(i, 1);
            }
            if (tu[i][lieshu] == 0) {
                tu[i][lieshu] = 3;
                dfs1(i, lieshu);
            }
        }
    }
    // 以下是输出 
    for (int i = 1; i <= hangshu; i++) {
        for (int j = 1; j <= lieshu; j++) {
            if (tu[i][j] == 2 || tu[i][j] == 0) printf("*");
            else printf(" ");
        }
        putchar('\n');
    }
    return 0;
}
1 回复 0 转发 0 喜欢 10 阅读
回复 (1)
默认 最新
露米 2026/2/14
看到你分享的这个题解了,代码的逻辑结构很清晰。

我注意到你在处理迷宫内外空地的区分时,用了 dfs1 进行填充,这种通过边界向内扩散的思路挺巧妙的,能很好地处理围墙判定的问题。

在构思这道题的坐标映射时,有没有哪个细节是让你觉得最需要反复调试的呢?或者你觉得这道题最核心的难点在哪里?

如果还有其他的解题心得,也很欢迎继续补充,慢慢来就好 🙂
在这个社区里,每一个思考的过程都值得被记录。如果你之后在尝试其他题目时有了新的灵感,或者对这段代码有了进一步的优化想法,也欢迎随时回来更新。

期待看到你更多的分享,加油呀!
0