【洛谷】P1162 填涂颜色题解（bfs，dfs）（一看就懂）

题目链接：填涂颜色 - 洛谷

思路：有三种颜色，一种是闭合圈上的“1” ，还有就是闭合圈里面的“0”，还有一种是闭合圈外面的“0”，要给闭合圈里面的“0”染色，而现在问题是不能区别“0”到底是在里面还是外面。

        其实我们如果能区分这个“0”是外面的“0”，那么我们也就知道了里面的“0”，相对于找里面的“0”，外面的“0”更加好找，只要找到一个外面的“0”，然后利用这个点dfs或是bfs就可以知道外面所有的“0”。但是会出现下图的情况，就是不存在外面的“0”。

        我们的方法是在外面加一圈“0”，我们手动创造外面的“0”，然后从外面的“0”开始就可以了。

#include <bits/stdc++.h>
typedef long long ll ;
using namespace std ;
const int maxn = 3e1 + 10 ;
const int inf = 0x3f3f3f3f ;
int a[maxn][maxn] , vis[maxn][maxn] ; 
int X[4] = {1 , 0 , -1 , 0} ;
int Y[4] = {0 , 1 , 0 , -1} ;
int n ; 
struct node{int x , y ;
};
bool judge(int x , int y){if(x < 0 || x > n+1 || y < 0 || y > n+1)return false ;if(vis[x][y] == 1 || a[x][y] == 1)return false ;return true ;
}
void bfs(int x , int y){queue<node > q ;node temp ;temp.x = x , temp.y = y ;q.push(temp) ;vis[x][y] = 1 ;while(!q.empty()){node t = q.front() ;a[t.x][t.y] = 2 ;//把边界0做标记 q.pop() ;for(int i = 0 ; i < 4 ; i++){int nx = t.x + X[i] ;int ny = t.y + Y[i] ;if(judge(nx , ny)){vis[nx][ny] = 1 ;temp.x = nx , temp.y = ny ;q.push(temp) ;}}}
}
void deal(){cin >> n ;for(int i = 1 ; i <= n ; i++)for(int j = 1 ; j <= n ; j++)cin >> a[i][j] ;bfs(0 , 0) ;for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= n ; j++){cout << 2-a[i][j] << " " ;}cout << "\n" ;}
} 
int main(){deal() ;return 0 ;
}