水池数目---深搜思想

水池数目---深搜思想
 1 //水池个数 深搜思想
 2 /*#include<stdio.h>
 3 int a[105][105],m,n;
 4 void DFS(int x,int y)
 5 {
 6     if(x<0||x>=m||y<0||y>=n)//到达边界
 7     return;
 8     if(a[x][y]!=0)//跳出
 9     {
10         a[x][y]=0;//搜完之后 此节点置0
11         DFS(x+1,y);//递归调用 往下搜
12         DFS(x,y+1);//右
13         DFS(x-1,y);//上
14         DFS(x,y-1);//左
15     }
16 }
17 int main()
18 {
19     int N,i,j;
20     scanf("%d",&N);
21     while(N--)
22     {
23         int sum=0;
24         scanf("%d%d",&m,&n);
25         for(i=0;i<m;i++)
26         for(j=0;j<n;j++)
27             scanf("%d",&a[i][j]);
28        for(i=0;i<m;i++)
29         for(j=0;j<n;j++)
30         {
31                 if(a[i][j]==1)//遇到 1 开始搜
32                 {
33                     DFS(i,j);
34                     sum++;
35                 }
36                 //printf("%d ",a[i][j]);
37 
38         }
39         printf("%d\n",sum);
40     }
41 }*/
水池数目---深搜思想

输入第一行输入一个整数N,表示共有N组测试数据
每一组数据都是先输入该地图的行数m(0<m<100)与列数n(0<n<100),然后,输入接下来的m行每行输入n个数,表示此处有水还是没水(1表示此处是水池,0表示此处是地面)输出输出该地图中水池的个数。
要注意,每个水池的旁边(上下左右四个位置)如果还是水池的话的话,它们可以看做是同一个水池。
样例输入

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

水池数目---深搜思想

上一篇:Java


下一篇:杨森翔书法:晨起日课(圆光7;条幅1)