[置頂] nyoj27 水池?cái)?shù)目
來源:程序員人生 發(fā)布時(shí)間:2015-05-27 08:25:28 閱讀次數(shù):2932次
水池?cái)?shù)目
時(shí)間限制:3000 ms | 內(nèi)存限制:65535 KB
難度:4
-
描寫
- 南陽理工學(xué)院校園里有1些小河和1些湖泊,現(xiàn)在,我們把它們通1看成水池,假定有1張我們學(xué)校的某處的地圖,這個(gè)地圖上僅標(biāo)識了此處是不是是水池,現(xiàn)在,你的任務(wù)來了,請用計(jì)算機(jī)算出該地圖中共有幾個(gè)水池。
-
輸入
-
第1行輸入1個(gè)整數(shù)N,表示共有N組測試數(shù)據(jù)
每組數(shù)據(jù)都是先輸入該地圖的行數(shù)m(0<m<100)與列數(shù)n(0<n<100),然后,輸入接下來的m行每行輸入n個(gè)數(shù),表示此處有水還是沒水(1表示此處是水池,0表示此處是地面) -
輸出
-
輸出該地圖中水池的個(gè)數(shù)。
要注意,每一個(gè)水池的旁邊(上下左右4個(gè)位置)如果還是水池的話的話,它們可以看作是同1個(gè)水池。
-
樣例輸入
-
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
-
思路: 本題是也是深搜中的經(jīng)典題目求區(qū)域的,與8連通求水洼問題相似,從每一個(gè)滿足條件的頂點(diǎn)開始深搜,求和。
-
本題代碼以下:
-
#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)//當(dāng)所有的點(diǎn)為0時(shí)說明這是1個(gè)水池
return;
s[i][j]=0;//每次搜索1個(gè)點(diǎn)后,置為0,避免重復(fù)
//從此點(diǎn)開始往4周擴(kuò)大
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++; //搜索結(jié)束后既為滿足條件
}
}
}
printf("%d
",ans);//輸出結(jié)果
}
return 0;
}
生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
------分隔線----------------------------
------分隔線----------------------------