a465: 12405 - Scarecrow
Tags :
Accepted rate : 439人/480人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 10:53

Content

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

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

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

Input

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

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

Output
對於每筆測資,先輸出測資編號,再輸出需放置的稻草人數量。
Sample Input
3
3
.#.
11
...##....##
2
##
Sample Output
Case 1: 1
Case 2: 3
Case 3: 0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Tags:
出處:
UVa12405 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」