【題目描述】

一個n * m的方格圖，一些格子被涂成了黑色，在方格圖中被標為1，白色格子標為0。問有多少個四連通的黑色格子連通塊。四連通的黑色格子連通塊指的是一片由黑色格子組成的區域，其中的每個黑色格子能通過四連通的走法（上下左右），只走黑色格子，到達該聯通塊中的其它黑色格子。

【輸入】

第一行兩個整數n,m(1≤n,m≤100)，表示一個n * m的方格圖。

接下來n行，每行m個整數，分別為0或1，表示這個格子是黑色還是白色。

【輸出】

一行一個整數ans，表示圖中有ans個黑色格子連通塊。

【輸入樣例】

3 3
1 1 1
0 1 0
1 0 1

【輸出樣例】

3

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 101 #define MOD 123 #define E 1e-6 using namespace std; struct node{int x;int y; }q[10100],p; int a[N][N],vis[N][N]; int next[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(vis[i][j]==0&&a[i][j]==1){cnt++;vis[i][j]=1;int head=1,tail=1;q[tail].x=i;q[tail].y=j;tail++;while(head<tail){p=q[head];for(int k=0;k<4;k++){int nx=p.x+next[k][0];int ny=p.y+next[k][1];if(vis[nx][ny]==0&&a[nx][ny]==1){vis[nx][ny]=1;q[tail].x=nx;q[tail].y=ny;tail++;}}head++;}}cout<<cnt<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的连通块（信息学奥赛一本通-T1335）的全部內容，希望文章能夠幫你解決所遇到的問題。

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