Problem Description
A while ago I had trouble sleeping. I used to lie awake, staring at the ceiling, for hours and hours. Then one day my grandmother suggested I tried counting sheep after I'd gone to bed. As always when my grandmother suggests things, I decided to try it out.
The only problem was, there were no sheep around to be counted when I went to bed.
Creative as I am, that wasn't going to stop me. I sat down and wrote a computer program that made a grid of characters, where # represents a sheep, while . is grass (or whatever you like, just not sheep). To make the counting a little more interesting, I also
decided I wanted to count flocks of sheep instead of single sheep. Two sheep are in the same flock if they share a common side (up, down, right or left). Also, if sheep A is in the same flock as sheep B, and sheep B is in the same flock as sheep C, then sheeps
A and C are in the same flock.
Now, I've got a new problem. Though counting these sheep actually helps me fall asleep, I find that it is extremely boring. To solve this, I've decided I need another computer program that does the counting for me. Then I'll be able to just start both these
programs before I go to bed, and I'll sleep tight until the morning without any disturbances. I need you to write this program for me.
Input
The first line of input contains a single number T, the number of test cases to follow.
Each test case begins with a line containing two numbers, H and W, the height and width of the sheep grid. Then follows H lines, each containing W characters (either # or .), describing that part of the grid.
Output
For each test case, output a line containing a single number, the amount of sheep flock son that grid according to the rules stated in the problem description.
Notes and Constraints
0 < T <= 100
0 < H,W <= 100
Sample Input
2
4 4
#.#.
.#.#
#.##
.#.#
3 5
###.#
..#..
#.###
Sample Output
6
3
数羊群的群数,“#”为羊,我们只要用BFS遍历把每一群标记即可
LANGUAGE:C
CODE
#include<stdio.h>
#define max 101
typedef struct
{
int x,y;
}node;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
char map[max][max];
int n,m,fx,fy;
void bfs()
{
node queue[max*max],cur,temp;
int rear=0,front=0,i,j;
cur.x=fx,cur.y=fy;
map[fx][fy]='.';
queue[rear++]=cur;
while(front<rear)
{
cur=queue[front++];
for(i=0;i<4;i++)
{
temp.x=cur.x+dir[i][0],temp.y=cur.y+dir[i][1];
if(temp.x>0&&temp.x<=n&&temp.y>0&&temp.y<=m&&map[temp.x][temp.y]=='#')
{
map[temp.x][temp.y]='.';
queue[rear++]=temp;
}
}
}
}
int main()
{
int i,j,k,t,count;
scanf("%d",&t); getchar();
for(i=0;i<t;i++)
{
scanf("%d%d",&n,&m);getchar();
for(j=1;j<=n;j++)
{
for(k=1;k<=m;k++)
{
scanf("%c",&map[j][k]);
}
getchar();
}
count=0;
for(j=1;j<=n;j++)
{
for(k=1;k<=m;k++)
{
if(map[j][k]=='#')
{
fx=j,fy=k;
bfs();
count++;
}
}
}
printf("%d\n",count);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
HDU的一题........HDU DP动态规
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu动态规划算法集锦
hdu 1166线段树代码
hdu题目分类
HDU图论题目分类
自己做的HDU ACM已经AC的题目
hdu 1005.比较简单的一道题,有兴趣的可以看看。