脚本宝典收集整理的这篇文章主要介绍了P1162填涂颜色,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
一.题目描述:
二.解题思路:
如果当前点是0的话跑一边bfs判断是否能到边界,如果能到边界,说明并没有形成闭合圈,反之则形成了,然后再跑一边bfs填颜色即可。
三.代码实现:
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",&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 }
以上是脚本宝典为你收集整理的P1162填涂颜色全部内容,希望文章能够帮你解决P1162填涂颜色所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。