洛谷P1162 填涂颜色【bfs】

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<map>
 4 #include<set>
 5 #include<iostream>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<vector>
 9 #include<queue>
10 
11 using namespace std;
12 
13 int n;
14 int mat[35][35];
15 typedef pair<int, int> pr;
16 int dx[4] = {-1, 1, 0, 0};
17 int dy[4] = {0, 0, -1, 1};
18 bool vis[35][35];
19 
20 bool check(int i, int j)
21 {
22     return (i >= 0 && j >= 0 && i < n && j < n);
23 }
24 
25 bool bfs(int i, int j)
26 {
27     memset(vis, 0, sizeof(vis));
28     queue<pr>que;
29     que.push(make_pair(i, j));
30     while(!que.empty()){
31         pr p = que.front();que.pop();
32         if(p.first == 0 || p.first == n - 1 || p.second == 0 || p.second == n - 1)return false;
33         for(int k = 0; k < 4; k++){
34             int x = p.first + dx[k], y = p.second + dy[k];
35             if(check(x, y) && mat[x][y] != 1 && !vis[x][y]){
36                 que.push(make_pair(x, y));
37                 vis[x][y] = true;
38             }
39             
40         }
41     }
42     return true;
43 }
44 
45 int main()
46 {
47     scanf("%d", &n);
48     for(int i = 0; i < n; i++){
49         for(int j = 0; j < n; j++){
50             scanf("%d", &mat[i][j]);
51         }
52     }
53     
54     for(int i = 0; i < n; i++){
55         for(int j = 0; j < n; j++){
56             if(mat[i][j] == 0){
57                 if(bfs(i, j)){
58                     mat[i][j] = 2;    
59                 }
60             }
61         }
62     }
63     
64     for(int i = 0; i < n; i++){
65         printf("%d", mat[i][0]);
66         for(int j = 1; j < n; j++){
67             printf(" %d", mat[i][j]);
68         }
69         printf("\n");
70     }
71     return 0;
72 }