没有用染色法,错了三个案例,求调

P1162 填涂颜色

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;
}

|