openjudge-最好的草

http://noi.openjudge.cn/ch0108/17/

总时间限制: 10000ms   单个测试点时间限制: 1000ms  内存限制: 65536kB

描述

奶牛Bessie计划好好享受柔软的春季新草。新草分布在R行C列的牧场里。它想计算一下牧场中的草丛数量。

在牧场地图中，每个草丛要么是单个“#”，要么是有公共边的相邻两个“#”。给定牧场地图，计算有多少个草丛。

例如，考虑如下5行6列的牧场地图

.#....
..#...
..#..#
...##.
.#....

这个牧场有5个草丛：一个在第一行，一个在第二列横跨了二、三行，一个在第三行，一个在第四行横跨了四、五列，最后一个在第五行。

输入

第一行包含两个整数R和C，中间用单个空格隔开。
接下来R行，每行C个字符，描述牧场地图。字符只有“#”或“.”两种。

输出

输出一个整数，表示草丛数。

样例输入

5 6

.#....

..#...

..#..#

...##.

.#....

样例输出

5

来源

USACO Open 2008 Bronze

解析：

广搜。具体步骤就是扫描二维数组，发现'#'号则从该坐标出发进行广搜，搜索的同时把搜过的'#'号修改为'.'   。

 #include <stdio.h>

 int count=,R,C;

 void bfs(char a[][],int i,int j);//从a[i][j]出发做bfs

 int main(int argc, char *argv[])

 {

     int i,j;

     char a[][];

     //freopen("17.in","r",stdin);

     //freopen("17.txt","w",stdout);

     scanf("%d%d",&R,&C);

     for(i=;i<R;i++) scanf("%s",a[i]);

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

     {

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

         {

             if(a[i][j]=='#') bfs(a,i,j);

         }

     }

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

     return ;

 }

 void bfs(char a[][],int i,int j)

 {

     int queueArr[][];

     int begin,end,number;//队头，队尾，队列元素数目

     int x,y,xx,yy;

     count++;//草块数目增加1

     a[i][j]='.';

     queueArr[][]=i;

     queueArr[][]=j;

     begin=;

     end=;

     number=;

     while(number>)//当队列不为空时继续循环

     {

         //读取队头元素的值

         x=queueArr[begin][];

         y=queueArr[begin][];

         //查询队头元素的周围节点是否'#'

         xx=x;

         yy=y-;

         if(yy>=&&a[xx][yy]=='#')

         {

             a[xx][yy]='.';

             queueArr[end][]=xx;

             queueArr[end][]=yy;

             end++;

             number++;

         }

         xx=x;

         yy=y+;

         if(yy<C&&a[xx][yy]=='#')

         {

             a[xx][yy]='.';

             queueArr[end][]=xx;

             queueArr[end][]=yy;

             end++;

             number++;

         }

         xx=x-;

         yy=y;

         if(xx>=&&a[xx][yy]=='#')

         {

             a[xx][yy]='.';

             queueArr[end][]=xx;

             queueArr[end][]=yy;

             end++;

             number++;

         }

         xx=x+;

         yy=y;

         if(xx<R&&a[xx][yy]=='#')

         {

             a[xx][yy]='.';

             queueArr[end][]=xx;

             queueArr[end][]=yy;

             end++;

             number++;

         }

         begin++;//队头出队

         number--;//队列元素数目减少1个

     }

 }

深搜代码：

 #include <stdio.h>

 int count=,R,C;

 char a[][];

 int dx[]={-,,,};//上下左右

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

 void dfs(int i,int j);//从a[i][j]出发做bfs

 int main(int argc, char *argv[])

 {

     int i,j;

     freopen("1.in","r",stdin);

     //freopen("1.txt","w",stdout);

     scanf("%d%d",&R,&C);

     for(i=;i<R;i++) scanf("%s",a[i]);

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

     {

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

         {

             if(a[i][j]=='#') { count++; dfs(i,j); }

         }

     }

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

     return ;

 }

 void dfs(int i,int j)//从a[i][j]出发做dfs

 {

     int xx,yy;

     a[i][j]='.';

     for(int k=;k<;k++)

     {

         xx=dx[k]+i;  yy=j+dy[k];

         if(xx>=&&xx<R&&yy>=&&yy<C&&a[xx][yy]=='#') dfs(xx,yy);

     }

 }

简化的广搜代码

 #include <stdio.h>

 int count=,R,C;

 int dx[]={-,,,};//上下左右

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

 void bfs(char a[][],int i,int j);//从a[i][j]出发做bfs

 int main(int argc, char *argv[])

 {

     int i,j;

     char a[][];

     freopen("1.in","r",stdin);

     //freopen("1.txt","w",stdout);

     scanf("%d%d",&R,&C);

     for(i=;i<R;i++) scanf("%s",a[i]);

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

     {

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

         {

             if(a[i][j]=='#') bfs(a,i,j);

         }

     }

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

     return ;

 }

 void bfs(char a[][],int i,int j)

 {

     int queueArr[][];

     int begin,end,number;//队头，队尾，队列元素数目

     int x,y,xx,yy;

     count++;//草块数目增加1

     a[i][j]='.';

     queueArr[][]=i;

     queueArr[][]=j;

     begin=;

     end=;

     number=;

     while(number>)//当队列不为空时继续循环

     {

         //读取队头元素的值

         x=queueArr[begin][];

         y=queueArr[begin][];

         //查询队头元素的周围节点是否'#'

         for(int k=;k<;k++)

         {

             xx=dx[k]+x; yy=dy[k]+y;

             if(xx>=&&xx<R&&yy>=&&yy<C&&a[xx][yy]=='#')

             {

                 a[xx][yy]='.';

                 queueArr[end][]=xx;

                 queueArr[end][]=yy;

                 end++;

                 number++;

             }

         }

         begin++;//队头出队

         number--;//队列元素数目减少1个

     }

 }

使用STL队列的广搜：

 #include<stdio.h>

 #include<queue>

 using namespace std;

 struct obj

 {

     int x,y;

 };

 int count=,R,C;

 int dx[]={-,,,};//上下左右

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

 void bfs(char a[][],int i,int j);//从a[i][j]出发做bfs

 int main(int argc, char *argv[])

 {

     int i,j;

     char a[][];

     freopen("1.in","r",stdin);

     //freopen("1.txt","w",stdout);

     scanf("%d%d",&R,&C);

     for(i=;i<R;i++) scanf("%s",a[i]);

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

     {

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

         {

             if(a[i][j]=='#') bfs(a,i,j);

         }

     }

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

     return ;

 }

 void bfs(char a[][],int i,int j)

 {

     int xx,yy;

     queue<struct obj> queA;

     struct obj temp;

     count++;//草块数目增加1

     a[i][j]='.';//访问当前出发点

     temp.x=i;

     temp.y=j;

     queA.push(temp);//出发点入队

     while(!queA.empty())//当队列不为空时继续循环

     {

         //查询队头元素的周围节点是否'#'

         for(int k=;k<;k++)

         {

             xx=dx[k]+queA.front().x;

             yy=dy[k]+queA.front().y;

             if(xx>=&&xx<R&&yy>=&&yy<C&&a[xx][yy]=='#')

             {

                 a[xx][yy]='.';

                 struct obj t;

                 t.x=xx;

                 t.y=yy;

                 queA.push(t);

             }

         }

         queA.pop();//删除队头

     }

 }

下面同样是使用了STL队列的广搜，不过在结构体定义时使用了结构体构造函数，可以看看：

 #include<stdio.h>

 #include<queue>

 using namespace std;

 struct obj

 {

     int x,y;

     obj(int xx,int yy){ x=xx;y=yy; }

     obj(){ x=;y=; }

 };

 int count=,R,C;

 int dx[]={-,,,};//上下左右

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

 void bfs(char a[][],int i,int j);//从a[i][j]出发做bfs

 int main(int argc, char *argv[])

 {

     int i,j;

     char a[][];

     freopen("1.in","r",stdin);

     //freopen("1.txt","w",stdout);

     scanf("%d%d",&R,&C);

     for(i=;i<R;i++) scanf("%s",a[i]);

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

     {

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

         {

             if(a[i][j]=='#') bfs(a,i,j);

         }

     }

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

     return ;

 }

 void bfs(char a[][],int i,int j)

 {

     int xx,yy;

     queue<struct obj> queA;

     struct obj temp;

     count++;//草块数目增加1

     a[i][j]='.';//访问当前出发点

     //temp.x=i;

     //temp.y=j;

     //queA.push(temp);//出发点入队

     queA.push(obj(i,j));

     while(!queA.empty())//当队列不为空时继续循环

     {

         //查询队头元素的周围节点是否'#'

         for(int k=;k<;k++)

         {

             xx=dx[k]+queA.front().x;

             yy=dy[k]+queA.front().y;

             if(xx>=&&xx<R&&yy>=&&yy<C&&a[xx][yy]=='#')

             {

                 a[xx][yy]='.';

                 //struct obj t;

                 //t.x=xx;

                 //t.y=yy;

                 //queA.push(t);

                 queA.push(obj(xx,yy));

             }

         }

         queA.pop();//删除队头

     }

 }