f005: 稻草人數量與位置
Tags :
Accepted rate : 18人/21人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-04-26 21:12

Content

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

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

已知田地的描述,要保護所有可用田地最少需要幾個稻草人?
且應在什麼位置放置稻草人。

Input

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

每筆測資第一行有一整數 N (0<N<100)。

下一行有 N 個字元以描述田地。點號(.)表示良田,井號(#)表示不毛之地。

Output

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

將位置輸出在數量後面的括號()內,位置之間以逗號 , 隔開。最左邊的位置編號為1。
若要保護的可用田地,有兩個位置的選項可以放置同一個稻草人時,則以位置編號較大者為放置位置。若不需要放置稻草人,則省略括號及位置的輸出。

Sample Input #1
3
3
.#.
11
...##....##
2
##
Sample Output #1
Case 1: 1(2)
Case 2: 3(2,7,10)
Case 3: 0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (33%): 1.0s , <1M
公開 測資點#1 (33%): 1.0s , <1M
公開 測資點#2 (34%): 1.0s , <1M
Hint :

不准作弊!

改編自UVa12405

Tags:
出處:
Caido2019學年度下學期延平中學國中組校內程式設計競賽 [管理者:
becaido (Caido)
]


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