thehanged @ 2024-04-26 13:12:42
就是暴力去看非边界的0能否到达边界,能到达边界就不在闭合圈内。
哪里有问题捏
#include <iostream>
using namespace std;
const int N = 35;
bool st[N][N];
char map[N][N];
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};
int n;
bool dfs(int x, int y){ // 从某个0开始搜索,在闭合圈内返回true
if(x == 1 || x == n || y == 1 || y == n){
return false;
}
// 标记当前位置搜索过
st[x][y] = true;
for(int i = 0; i < 4; ++ i){
int tx = x + dx[i], ty = y + dy[i];
if(tx <= 0 || tx > n || ty <= 0 || ty >= n) continue;
if(!st[tx][ty] && map[tx][ty] == '0'){
if(!dfs(tx, ty)) return false; // 找到一条到达边界的路径,不在闭合圈内
}
}
map[x][y] = '2';
return true;
}
int main(){
cin >> n;
for(int i = 1; i <= n; ++ i){
int t;
for(int j = 1; j <= n; ++ j)
cin >> t, map[i][j] = t + '0';
}
for(int i = 2; i < n; ++ i)
for(int j = 2; j < n; ++ j)
if(!st[i][j] && map[i][j] == '0')
dfs(i, j);
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= n; ++ j)
putchar(map[i][j]), putchar(' ');
puts("");
}
return 0;
}