a465. 12405 - Scarecrow - 高中生程式解題系統

Content

Taso 有一塊條狀的田地。他計劃在下一季種植不同的作物。但是這個地區有很多烏鴉，Taso 怕他們會吃掉這些作物。因此他決定在田地的不同位置放置稻草人。

田地可以用 1 x 𝑁 的格子模擬。有些部分是不毛之地無法種植作物。一個稻草人除了所在的格子外也保護其左側及右側緊鄰的格子。

已知田地的描述，要保護所有可用田地最少需要幾個稻草人？

Input

輸入開始有一整數 𝑇 (≤ 100)，表示測資筆數。

每筆測資第一行有一整數 𝑁 (0 < 𝑁 < 100)。下一行有 𝑁 個字元以描述田地。點 (.) 表示良田，井號 (#) 表示不毛之地。

Output

對於每筆測資，先輸出測資編號，再輸出需放置的稻草人數量。

Sample Input #1

3
3
.#.
11
...##....##
2
##

Sample Output #1

Case 1: 1
Case 2: 3
Case 3: 0

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (100%): 1.0s , <1M

Hint ：

Tags:

出處:

UVa 12405 [管理者： snail (蝸牛) ]