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

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

#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
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!