P1162填涂颜色

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 int mp[35][35];
 4 int bk[35][35];
 5 int mv[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
 6 int n;
 7 int flag;
 8 struct node{int x;int y;};
 9 void full_color(int sx,int sy)
10 {
11     queue <node> ans;
12     int head = 1,tail = 1;
13     node u;
14     u.x = sx;
15     u.y = sy;
16     bk[sx][sy] = 1;
17     tail++;
18     ans.push(u);
19     while(head < tail){
20         node v = ans.front();
21         mp[v.x][v.y] = 2;
22         ans.pop();
23         for(int i = 0;i < 4;i++){
24             int dx = v.x + mv[i][0];
25             int dy = v.y + mv[i][1];
26             if(mp[dx][dy] == 1 || bk[dx][dy]) conTinue;
27             if(dx <= 0 || dx >= n - 1 || dy <= 0 || dy >= n - 1)conTinue;
28             node w;
29             w.x = dx;
30             w.y = dy;
31             bk[dx][dy] = 1;
32             ans.push(w);
33             tail++;
34         }
35         head++;
36     }
37 }
38 void find_edge(int sx,int sy)
39 {
40     queue <node> ans;
41     int head = 1,tail = 1;
42     node u;
43     u.x = sx;
44     u.y = sy;
45     bk[sx][sy] = 1;
46     tail++;
47     ans.push(u);
48     while(head < tail){
49         node v = ans.front();
50         ans.pop();
51         for(int i = 0;i < 4;i++){
52             int dx = v.x + mv[i][0];
53             int dy = v.y + mv[i][1];
54             if(mp[dx][dy] == 1 || bk[dx][dy]) conTinue;
55             if(dx <= 0 || dx >= n - 1 || dy <= 0 || dy >= n - 1){flag = 1; return;}
56             node w;
57             w.x = dx;
58             w.y = dy;
59             bk[dx][dy] = 1;
60             ans.push(w);
61             tail++;
62         }
63         head++;
64     }
65 }
66 int main()
67 {
68     cin >> n;
69     for(int i = 0;i < n;i++)
70         for(int j = 0;j < n;j++)
71             scanf("%d",&@H_781_40@mp[i][j]);
72     for(int i = 0;i < n;i++){
73         int j;
74         for(j = 0;j < n;j++)
75             if(mp[i][j] == 0 && i != 0 && i != n - 1 && j != 0 && j != n - 1){
76                 flag = 0;
77                 bk[i][j] = 1;
78                 find_edge(i,j);
79                 for(int l = 0;l < n;l++)
80                     for(int m = 0;m < n;m++)
81                         bk[l][m] = 0;
82                 if(!flag){
83                     full_color(i,j);
84                     break;
85                 }
86             }
87         if(!flag && j != n) break;
88     }
89     for(int i = 0;i < n;i++){
90         for(int j = 0;j < n;j++)
91             cout << mp[i][j] << ' ';
92         cout << endl;
93     }
94     return 0;
95 }