nyoj27-水池数目（求连通块数目）【dfs】

http://acm.nyist.net/JudgeOnline/problem.php?pid=27

水池数目

时间限制：3000 ms | 内存限制：65535 KB

难度：4

描述: 南阳理工学院校园里有一些小河和一些湖泊，现在，我们把它们通一看成水池，假设有一张我们学校的某处的地图，这个地图上仅标识了此处是否是水池，现在，你的任务来了，请用计算机算出该地图中共有几个水池。

输入

第一行输入一个整数N，表示共有N组测试数据
每一组数据都是先输入该地图的行数m(0<m<100)与列数n(0<n<100)，然后，输入接下来的m行每行输入n个数，表示此处有水还是没水（1表示此处是水池，0表示此处是地面）

输出

输出该地图中水池的个数。
要注意，每个水池的旁边（上下左右四个位置）如果还是水池的话的话，它们可以看做是同一个水池。

样例输入

样例输出

2

3

题意：就是求这个二维地图上由1组成的连通块的数目。

题解1：dfs

 #include <fstream>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int N=;

 int m,n,ans;

 int a[N][N];

 bool b[N][N];

 int xy[][]={{,-,,},{,,,-}};

 bool check(int x,int y);

 void dfs(int x,int y);

 int main()

 {

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     int T;

     scanf("%d",&T);

     while(T--){

         ans=;

         scanf("%d%d",&m,&n);

         for(int i=;i<m;i++)

             for(int j=;j<n;j++)

                 scanf("%d",&a[i][j]);

         memset(b,,sizeof(b));

         for(int i=;i<m;i++)

             for(int j=;j<n;j++)

                 if((!b[i][j])&&a[i][j])    dfs(i,j),ans++;

         printf("%d\n",ans);

     }

     return ;

 }

 bool check(int x,int y){

     return x>=&&x<m&&y>=&&y<n&&b[x][y]==;

 }

 void dfs(int x,int y){

     b[x][y]=;

     if(!a[x][y])    return;

     int tx,ty;

     for(int i=;i<;i++){

         tx=x+xy[][i];

         ty=y+xy[][i];

         if(check(tx,ty))  dfs(tx,ty);

     }

 }

题解2：非递归方式：队列。建立队列q，遍历二维图所有点，对每个点扩展的点存入队列，再一一处理。

 #include <stdio.h>

 int main()

 {

     int t,n,m,e=,i,j,k,s,num,q[],r[][];

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&n,&m);

         for(i=;i<n;i++)

             for(j=;j<m;j++)

                 scanf("%d",&r[i][j]);

         num=;

         for(i=;i<n;i++)

             for(j=;j<m;j++)

             {

                 if(r[i][j]==)

                 {

                     int a,b;

                     a=i;

                     b=j;

                     k=;

                     s=;

                     while(s<k)

                     {

                         if(r[a][b-]==)

                         {

                             q[k++]=a*e+b-;

                             r[a][b-]=;

                         }

                         if(r[a][b+]==)

                         {

                             q[k++]=a*e+b+;

                             r[a][b+]=;

                         }

                         if(r[a-][b]==)

                         {

                             q[k++]=(a-)*e+b;

                             r[a-][b]=;

                         }

                         if(r[a+][b]==)

                         {

                             q[k++]=(a+)*e+b;

                             r[a+][b]=;

                         }

                         a=q[++s]/e;

                         b=q[s]%e;

                     }

                     num++;

                 }

             }

         printf("%d\n",num);

     }

     return ;

 }

水池

nyoj27-水池数目 （求连通块数目）【dfs】

水池数目

nyoj27-水池数目（求连通块数目）【dfs】