41 . 庭院裡的水池

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

$\Hugeℎ𝑢𝑛𝑔$
$\Huge\textcolor{orange}{早安} \quad\Large\textcolor{green}{呱}$

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

100.0% (5/5)

Tags

Algo Algo25_a

Description

$μzk$ 家有很大的庭院，庭院裡面有很多灘的水池，現在 $μzk$ 打算計算他的庭院中有多少灘水池。一個有水的格子與它相鄰的四個方向中有水的格子都算是同一灘水池，水池間可能會被一些非水池的障礙物隔開。

下圖是一個兩灘水池的例子，左上方的單一格視為一灘水池，右下方的三格皆相鄰也視為同一灘水池。

Input Format

輸入的第一行有一個整數 $T$，代表接下來有 $T$ 筆測試資料。


每筆測試資料的第一行且包含兩個整數 $H,W$，代表這個水池的高與寬。接下來有 $H$ 行，每行包含 $W$ 個字元表示此張地圖，# 為障礙物，. 為水池。

  • $T\leq 10$
  • $1\leq W,H\leq 1000$

Output Format

對每筆測試資料輸出有多少灘不同的水池。

Sample Input 1

4
3 4
.###
###.
##..
4 4
.###
#.##
##.#
###.
4 4
..##
#.##
#...
##..
4 4
.###
#..#
#..#
###.

Sample Output 1

2
4
1
3

Hints

下圖分別為範例輸入中第 $2,3,4$ 筆的水池分法：

　　　　

Problem Source

NEOJ Problem 42

Subtasks

No. Testdata Range Constraints Score
1 0~2 $1\leq W,H\leq 10$，且保證邊界不會有水池 30
2 0~9 無額外限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 131072 65536 1 2
1 2000 131072 65536 1 2
2 2000 131072 65536 1 2
3 2000 131072 65536 2
4 2000 131072 65536 2
5 2000 131072 65536 2
6 2000 131072 65536 2
7 2000 131072 65536 2
8 2000 131072 65536 2
9 2000 131072 65536 2
Submit
Back to Top