題目鏈接：https://www.luogu.org/problemnew/show/P1162

---

?

好久沒寫博客了，這次一寫竟是道搜索模板題。可見我水平下降很快。。。

這道題雖然簡單，但細節頗多，需要注意的東西不少。雖然是用搜索找連通塊，但起點怎么找呢？其實找內部的點不如找外部的點，反正只是要把幾個連通塊區分開。本以為這樣就可以對，實際實現時卻忽略了兩點，可能沒有外部的點，即1占滿了邊界；可能不止3個連通塊，外部點可能不連通。

1 #include<cstdio> 2 #include<queue> 3 using namespace std; 4 const int maxn=35; 5 const int mov[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 6 int n,mt[maxn][maxn]; 7 struct point { 8 int x,y; 9 point(int x,int y):x(x),y(y) {} 10 }; 11 queue<point> q; 12 void bfs(int sx,int sy) { 13 q.push(point(sx,sy)); 14 while(!q.empty()) { 15 int nx=q.front().x,ny=q.front().y;q.pop(); 16 mt[nx][ny]=2; 17 for(int i=0;i<4;++i) { 18 int a=nx+mov[i][0],b=ny+mov[i][1]; 19 if(mt[a][b]||a<1||a>n||b<1||b>n) continue; 20 q.push(point(a,b)); 21 } 22 } 23 } 24 int main() { 25 scanf("%d",&n); 26 for(int i=1;i<=n;++i) 27 for(int j=1;j<=n;++j) scanf("%d",&mt[i][j]); 28 for(int i=1;i<=n;++i) { 29 if(!mt[1][i]) bfs(1,i); 30 if(!mt[i][1]) bfs(i,1); 31 if(!mt[n][i]) bfs(n,i); 32 if(!mt[i][n]) bfs(i,n); 33 } 34 for(int i=1;i<=n;++i) { 35 if(i!=1) putchar('\n'); 36 for(int j=1;j<=n;++j) { 37 if(j!=1) putchar(' '); 38 if(!mt[i][j]) printf("2"); 39 else if(mt[i][j]==1) printf("1"); 40 else printf("0"); 41 } 42 } 43 return 0; 44 } AC代碼

?

轉載于:https://www.cnblogs.com/Mr94Kevin/p/9691914.html

總結

以上是生活随笔為你收集整理的【洛谷习题】填涂颜色的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。