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

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

#include<bits/stdc++.h>

using namespace std;

char mmap[220][220]; //开220的数组 从中心(110,110)开始移动防止越界 
string route;
int n;
bool flag[220][220];
int d[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};
int bx1,bx2,by1,by2;
bool outcheck[220][220]; 

bool check(int x,int y){ //验证一个既不是空地也不是墙的点是否连接边界 
    queue <pair<int,int>> q;
    q.push({x,y});
    outcheck[x][y] = true;
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        int ox = t.first,oy=t.second;
        if(ox == bx1  || ox == bx2 || oy == by1 || oy == by2 ){
            return false; //边界联通,为外 
        }
        for(int i = 0 ; i<4;i++){
            int nx = ox + d[i][0],ny = oy+d[i][1];
            if(!flag[nx][ny] && !outcheck[nx][ny]){
                q.push({nx,ny});
                outcheck[nx][ny] = true;
            }
        }
    }
    return true;//在墙内 
}


int main(){
    cin >> n;
    cin >> route;
    int x = 110,y=110;
    bx1 = 110;
    bx2 = 110; 
    by1 = 110;
    by2 = 110;
    map<char,pair<int,int>> order;
    order['U'] = {-1,0};
    order['L'] = {0,-1};
    order['D'] = {1,0};
    order['R'] = {0,1};
    flag[x][y] = true;
    mmap[x][y] = ' ';
    for(int i = 0 ; i<220;i++){
    	for(int j = 0 ; j<220;j++){
    		mmap[i][j] = ' ';
		}
	}
    flag[x][y] = true;
    mmap[x][y] = ' ';
    for(int j = 0 ; j<4 ; j++){
        int nx = x + d[j][0];
        int ny = y + d[j][1];
        if(!flag[nx][ny]){
            flag[nx][ny] = true;
            mmap[nx][ny] = '*';
        }
        if(nx < bx1) bx1 = nx;
        if(nx > bx2) bx2 = nx;
        if(ny < by1) by1 = ny;
        if(ny > by2) by2 = ny;  
    } //初始点处理 
	
	
    for(int i = 0; i<=n;i++){ 
        x = x + order[route[i]].first;
        y = y + order[route[i]].second;
        flag[x][y] = true;
        mmap[x][y] = ' ';
        for(int j = 0 ; j<4 ; j++){
            int nx = x + d[j][0];
            int ny = y + d[j][1];
            if(!flag[nx][ny]){
                flag[nx][ny] = true;
                mmap[nx][ny] = '*';
            }
            if(nx < bx1) bx1 = nx;
            if(nx > bx2) bx2 = nx;
            if(ny < by1) by1 = ny;
            if(ny > by2) by2 = ny;
        }
    }//移动后处理 
    for(int i = bx1;i<=bx2;i++){
        for(int j = by1;j<=by2;j++){
            if(check(i,j) && !flag[i][j]){
                mmap[i][j] = '*';
            }
            memset(outcheck,false,sizeof(outcheck));
        }
    } //验证未访问的点是外界 还是需要补墙 
    for(int i = bx1;i<=bx2;i++){
        for(int j = by1;j<=by2;j++){
            cout << mmap[i][j];
        }
        cout << endl;
    }
    return 0;
}

//23
//RRRRRUULLLLDDDDDRRURRDD
1 回复 0 转发 0 喜欢 5 阅读
回复 (1)
默认 最新
露米 2026/3/5
这份题解的思路很清晰,谢谢分享。

从中心点开始移动来防止越界是一个很细心的小技巧。在处理“封闭空间”时,你选择用 BFS 去逐个验证点是否连接边界,这个逻辑非常直观。

我注意到在最后验证墙内外的时候,每个点都会进行一次搜索并配合 memset。如果地图尺寸变大,这部分可能会稍微有些耗时。你觉得如果尝试从最外层边界开始做一次整体的“染色”搜索,会不会更高效一点?

期待看到你更多的思路 🙂
另外,在处理路径循环的边界(比如 i <= n)时,或许可以再微调一下,避免读到字符串末尾之外的内容。

如果你在尝试优化或者遇到了其他有趣的题目,随时欢迎回来交流,我会在这里陪着大家一起进步的。加油!
0