[置頂] nyoj27 水池數目

描寫

南陽理工學院校園里有1些小河和1些湖泊，現在，我們把它們通1看成水池，假定有1張我們學校的某處的地圖，這個地圖上僅標識了此處是不是是水池，現在，你的任務來了，請用計算機算出該地圖中共有幾個水池。

輸入

第1行輸入1個整數N，表示共有N組測試數據
每組數據都是先輸入該地圖的行數m(0<m<100)與列數n(0<n<100)，然后，輸入接下來的m行每行輸入n個數，表示此處有水還是沒水（1表示此處是水池，0表示此處是地面）

輸出

輸出該地圖中水池的個數。
要注意，每一個水池的旁邊（上下左右4個位置）如果還是水池的話的話，它們可以看作是同1個水池。

樣例輸入

2 3 4 1 0 0 0 0 0 1 1 1 1 1 0 5 5 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1

樣例輸出

2 3

思路： 本題是也是深搜中的經典題目求區域的，與8連通求水洼問題相似，從每一個滿足條件的頂點開始深搜，求和。

本題代碼以下：

#include<stdio.h> #include<string.h> int s[101][101],n,m; void dfs(int i,int j) { if(i<0||i>m||j<0||j>n||s[i][j]==0)//當所有的點為0時說明這是1個水池 return; s[i][j]=0;//每次搜索1個點后，置為0，避免重復 //從此點開始往4周擴大 dfs(i,j+1); dfs(i,j⑴); dfs(i⑴,j); dfs(i+1,j); } int main() { int N; scanf("%d",&N); while(N--) { int i,j,ans=0; memset(s,0,sizeof(s));//初始化，0表示地面，1表示水池 scanf("%d%d",&m,&n); for(i=0;i<m;i++) { for(j=0;j<n;j++) scanf("%d",&s[i][j]); } for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(s[i][j]==1)//每次從是水池的地方開始深搜 { dfs(i,j); ans++; //搜索結束后既為滿足條件 } } } printf("%d ",ans);//輸出結果 } return 0; }

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈