題目描述

有一個 N x M 的棋板，沒有棋的地方用字符「*」表示，有棋的地方用字符「A」表示，每一顆棋子可以和上下左右四個方向緊接著一起的棋子相連，現在想大家幫忙寫一個程序，可以計算出有多少塊連接的棋。

輸入格式

第一行有一個整數 T，代表測試次數。( 1 <= T <= 10 )

第次測試的第一行有兩個整數 N, M，用一個空格分隔。 ( 1 <= N, M <= 1000 )
隨後共有 N 行，每行有 M 個字符，分別都有一個空格分隔。

輸出格式

每次測試都輸出一個整數，代表棋塊的數量。

Samples

2
5 6
* A A * * *
A A * A * *
A * A A A A
A * * * * *
* * A A * *
3 3
A * A
* A *
A * A

3
5

提示

棋塊示例：

* A A * * *      * 1 1 * * *
A A * A * *      1 1 * 2 * *
A * A A A A  =>  1 * 2 2 2 2  => 所以答案為 3 塊棋
A * * * * *      1 * * * * *
* * A A * *      * * 3 3 * *

 

A * A      1 * 2
* A *  =>  * 3 * => 所以答案為 5 塊棋
A * A      4 * 5

測試數據：

#1, #2, #3, #4 ( 1 <= n, m <= 10 )

#5, #6, #7, #8 ( 10 < n, m <= 100 )

#9, #10 ( 100 < n, m <= 1000 )

備註

枚舉法、洪水填充法 https://web.ntnu.edu.tw/~algo/AlgorithmDesign.html#3

原始資料

• Zero1 題號：a612
• Hydro 題號：Z0612
• Locale：zh_TW
• Display：practice