P1162 填涂颜色

这题在做之前要先证明一个结论：如果一个0没有被包围在圈内，那么存在一个边缘的0和它连通。
证明的前提：有且只有一个的圈，并且这个圈是合法的
显然有：某一个0和任意一个边缘的0不连通（也就是说从这个0出发的任何路径都到不了边缘的任意一个0） -> 它一定被包围在圈内，从而由逆否命题获证原命题正确

#include<iostream>

using namespace std;

const int N = 40;

int st[N][N];
int g[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int n;
int flag;

void dfs(int x, int y){
    st[x][y] = 1;
    
    for(int i = 0; i < 4; i ++){
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || b < 0 || a >= n || b >= n) continue;
        if(st[a][b] || g[a][b]) continue;
        dfs(a, b);
    }
}

int main(){
    cin >> n;
    
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> g[i][j];
    
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            if(i == 0 || j == 0 || i == n - 1 || j == n - 1)
                if(g[i][j] == 0 && st[i][j] == 0) dfs(i, j);
            
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++)
            if(st[i][j] || g[i][j]) cout << g[i][j] << ' ';
            else cout << 2 << ' ';
        cout << endl;
    }
            
    return 0;
}