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
解析：
广搜。具体步骤就是扫描二维数组，发现'#'号则从该坐标出发进行广搜，搜索的同时把搜过的'#'号修改为'.' 。
1 #include <stdio.h> 2 int count=0,R,C; 3 void bfs(char a[105][105],int i,int j);//从a[i][j]出发做bfs 4 int main(int argc, char *argv[]) 5 { 6 int i,j; 7 char a[105][105]; 8 //freopen("17.in","r",stdin); 9 //freopen("17.txt","w",stdout); 10 scanf("%d%d",&R,&C); 11 for(i=0;i<R;i++) scanf("%s",a[i]); 12 13 for(i=0;i<R;i++) 14 { 15 for(j=0;j<C;j++) 16 { 17 if(a[i][j]=='#') bfs(a,i,j); 18 } 19 } 20 printf("%d\n",count); 21 return 0; 22 } 23 void bfs(char a[105][105],int i,int j) 24 { 25 int queueArr[10010][2]; 26 int begin,end,number;//队头，队尾，队列元素数目 27 int x,y,xx,yy; 28 29 count++;//草块数目增加1 30 31 a[i][j]='.'; 32 queueArr[0][0]=i; 33 queueArr[0][1]=j; 34 begin=0; 35 end=1; 36 number=1; 37 38 while(number>0)//当队列不为空时继续循环 39 { 40 //读取队头元素的值 41 x=queueArr[begin][0]; 42 y=queueArr[begin][1]; 43 44 //查询队头元素的周围节点是否'#' 45 xx=x; 46 yy=y-1; 47 if(yy>=0&&a[xx][yy]=='#') 48 { 49 a[xx][yy]='.'; 50 queueArr[end][0]=xx; 51 queueArr[end][1]=yy; 52 end++; 53 number++; 54 } 55 56 xx=x; 57 yy=y+1; 58 if(yy<C&&a[xx][yy]=='#') 59 { 60 a[xx][yy]='.'; 61 queueArr[end][0]=xx; 62 queueArr[end][1]=yy; 63 end++; 64 number++; 65 } 66 67 xx=x-1; 68 yy=y; 69 if(xx>=0&&a[xx][yy]=='#') 70 { 71 a[xx][yy]='.'; 72 queueArr[end][0]=xx; 73 queueArr[end][1]=yy; 74 end++; 75 number++; 76 } 77 78 xx=x+1; 79 yy=y; 80 if(xx<R&&a[xx][yy]=='#') 81 { 82 a[xx][yy]='.'; 83 queueArr[end][0]=xx; 84 queueArr[end][1]=yy; 85 end++; 86 number++; 87 } 88 89 begin++;//队头出队 90 number--;//队列元素数目减少1个 91 } 92 }
