【回忆迷宫——处理方法+DFS】

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 250;
int g[N][N];
bool vis[N][N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int nx = 999, ny = 999, mx, my;
int x = 101, y = 101; //0墙 (1空地 2远方)
bool jud(int x, int y)
{if(vis[x][y]) return false;if(x < nx || x > mx || y < ny || y > my) return false;for(int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];if(g[nx][ny] == 1) return false;}return true;
}
void dfs(int x, int y)
{vis[x][y] = 1;g[x][y] = 2;for(int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];if(jud(nx, ny)) dfs(nx, ny);}
}
int main()
{int n;cin >> n;nx = min(nx, x); ny = min(ny, y);mx = max(mx, x); my = max(my, y);g[x][y] = 1; //这一句本来应该不用，感觉数据有问题for(int i = 1; i <= n; i++){char c;cin >> c;if(c == 'U') x--;else if(c == 'L') y--; else if(c == 'D') x++;else if(c == 'R') y++;g[x][y] = 1;nx = min(nx, x); ny = min(ny, y);mx = max(mx, x); my = max(my, y);}nx--, ny--, mx++, my++;for(int i = nx; i <= mx; i++){if(jud(i, ny)) dfs(i, ny);if(jud(i, my)) dfs(i, my);}for(int i = ny; i <= my; i++){if(jud(nx, i)) dfs(nx, i);if(jud(mx, i)) dfs(mx, i);}for(int i = nx; i <= mx; i++){for(int j = ny; j <= my; j++){if(g[i][j] == 0) cout << '*';else cout << ' ';}cout << '\n';}
}