Counting Sheep

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1727    Accepted Submission(s): 1121

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

 

Source

 

Recommend

gaojie

 

思路：

 

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <queue>

#include <cstring>

using namespace std

;

int hash

[

110

][

110

];

char map

[

110

][

110

];

int bfs

[

4

][

2

] = {

1

,

0

,-

1

,

0

,

0

,

1

,

0

,-

1

};

int t

,h

,w

;

int sum

;

int a

,b

;

struct Node

{

    int x

,y

;

};

void BFS

()

{

    queue

< Node

> q

;

    Node top

;

    top

.x

= a

;top

.y

= b

;

    q

.push

(top

);

    while

(!q

.empty

())

    {

        Node temp

;

        temp

= q

.front

();

        q

.pop

();

        for

(

int i

=

0

;i

<

4

;i

++)

        {

            int x

= temp

.x

+ bfs

[i

][

0

],y

= temp

.y

+ bfs

[i

][

1

];

            if

(map

[x

][y

] ==

'#'

&& hash

[x

][y

] ==

0

&&

            x

>=

1

&& x

<= h

&& y

>=

1

&& y

<= w

)

            {

                Node xin

;

                xin

.x

= x

;xin

.y

= y

;

                hash

[x

][y

] =

1

;

                q

.push

(xin

);

            }

        }

    }

}

int

main

()

{

    scanf

(

"%d"

,&t

);

    while

(t

--)

    {

        memset

(hash

,

0

,

sizeof

(hash

));

        scanf

(

"%d%d"

,&h

,&w

);

        for

(

int i

=

1

;i

<= h

;i

++)

            for

(

int j

  =

1

;j

<= w

;j

++)

                scanf

(

" %c"

,&map

[i

][j

]);

        sum

=

0

;

        for

(

int i

=

1

;i

<= h

;i

++)

            for

(

int j

=

1

;j

<= w

;j

++)

               if

(map

[i

][j

] ==

'#'

&& hash

[i

][j

] ==

0

)

               {

                  sum

++;

                  a

= i

;b

= j

;

                  BFS

();

                }

        printf

(

"%d\n"

,sum

);

    }

}