NYOJ--第27题 水池数目

这个题我提供两种方法，一种深度搜索，一种广度搜索。这个题是学校OJ上比较简单的搜索题，昨天晚上学长给简单的讲了讲搜索，所以今天就拿这个来练手了，因为跟队友分好，我弄搜索，他弄背包。我需要在搜索上多下点工夫，所以今天一整天都在弄这个问题，其实很是简单，现在想明白之后就会发现很没难度。因为有管理权限，所以我可以看到很多人的代码。但是发现很少有人用广搜。我用深搜做完之后觉得用广搜在理论上也可以实现，所以一下午的时间都在那敲代码，调试程序，不断的找错误。现在把广搜和深搜的代码都贴出来。现在把解体思路写在代码中了，供后来者看，当然也欢迎大牛们赐教。

原题地址：

代码如下：

一、深度搜索（代码比较简单，但是不怎么好理解）

#include<stdio.h>//*深搜*//
#include<iostream>
#include<string.h>
//#include<queue>
using namespace std;
int s,t,a[105][105];//*数组定义在函数外面，不然你会很悲剧的发现自己的程序无法输入数据。*//
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};//*此乃周围四个点的坐标集合。用两个数组来储存*//
void dfs(int m,int n)//*调用函数，bfs*//
{
	a[m][n]=0;//*将搜索过的标记成陆地*//
	for(int k=0;k<4;k++)
	 {s=m+dx[k];
	   t=n+dy[k];
	 if(a[s][t])//*当四周有水池的时候，再次搜索其他方位的、*//
		 dfs(s,t);//*不断的调用函数，继续往下一深度搜索，直到把周围的全部搜完*//
	}
}
int main()
{
	int i,j,s,n,m;
	scanf("%d",&s);
	while(s--)
	{   int count=0;
		scanf("%d%d",&m,&n);
		memset(a,0,sizeof(a));//*一定要记得清零。*//
		for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
		for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		  if(a[i][j])
		    { dfs(i,j);//*不断的调用函数*//
		      count++;}
		printf("%d\n",count);
	}return 0;
}

二、广度搜索（这个比较好理解，但是代码很长）

<span style="font-size: 18px;">#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
int a[101][101];//*大点的数组还是要定义在外面*//
int b[4][2]={-1,0,1,0,0,-1,0,1};//*这个也是标记四个方向的坐标，不过这个只用了一个数组*//
struct num//*定义队列元素*//
{
	int x,y;
};
queue<num>Q;//*建立一个队列*//
int bfs(int n,int m)
{
	int i,j,s,t,k=0;
	for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
	{
	 if(a[i][j])//*判断是否是陆地或者已经搜索过*//		
	  { 
			 k++;//*统计次数*//
			 num e={i,j};
	         Q.push(e);
	         a[i][j]=0;
	     while(!Q.empty())
	     {
		       e=Q.front();
		       Q.pop();
		   for(int l=0;l<4;l++)//*此处是我悲剧的源泉啊！！一个函数中多次使用同一变量*//
		   { 
			s=e.x+b[l][0];
			t=e.y+b[l][1];
			if(s>0&&s<=n&&t>0&&t<=m&&a[s][t])//*判断边界*//
			{
				num e1={s,t};
				Q.push(e1);//*满足条件的放入队列中*//
				a[s][t]=0;//*标记*//
		   	}
     	   }
	     }					
          while(!Q.empty())//*清空队列*//
	      Q.pop();
	   }
	 }return k;//*返回所求的次数*//
}
int main()
{  
	int i,j,k,l,s,n,m;
	scanf("%d",&s);
	while(s--)
	{   
		memset(a,0,sizeof(a));
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
			printf("%d\n",bfs(n,m));//*直接调用函数，说出结果*//
	}return 0;
}</span>

其实比较这两串代码你会发现这里面的思想是相同的，不断的对周围的数据进行处理，唯一不同的就是处理的顺寻不同。不过我发现通过这种方式其实可以发现自己很多的不足，今天下午悲剧的原因，究其根本还是自己的基础不够扎实啊，竟然可以在同一个函数中多次用到了i，纠结了整整两个小时啊！！！！

好了，不再这废话了，我只是希望你们看到这串代码之后自己能够有所启发，可能解释的不够仔细，如果那个 地方不够明白可以直接给我留言。

还是那句话;

路漫漫其修远兮，吾将上下而求索！