문제1613--Islands

### 1613: Islands

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 97  통과: 76
[제출] [채점기록] [묻고답하기]

#### 문제 설명

The king is trying to find new ways to generate revenue, and he is currently exploring tourism as one potential avenue. The kingdom is a group of islands, and the amount of revenue that can be generated depends on the combined total length of beaches on all the islands.

You are given a String[] kingdom consisting of '.' or '#' characters. '#' represents a land mass, whereas '.' represents water. kingdom[i][j] represents a regular-hexagon shaped area with each side of unit length. Since the cells are hexagonal in shape, the odd-numbered rows (0-based) are 'shifted' towards the right. A beach is a segment which has water on one side, and land on the other.

An example String[] and the corresponding image are given below to illustrate. The beaches are marked in red.

{"..#.##",  ".##.#.",  "#.#..."}

Print the combined total length of beaches on all the islands.

#### 입력 설명

The first line of the input gives the number of test cases, T (1 <= T <= 200).

Each test case starts with two positive integers rc, representing number of rows and columns of kingdom, respectively. R and c is between 1 and 50, inclusive.

For next r lines, length c string representing r-th line of kingdom is given. Each character of the string will be either '.' or '#'.

#### 출력 설명

For each test case, print the number as explained in the problem statement, in one line.

4
1 8
.#...#..
3 6
..#.##
.##.#.
#.#...
2 10
#...#.....
##..#...#.
4 6
....#.
.#....
..#..#
####..

4
19
15
24