內容
有個學校想辦一場考試，提供了 T 間教室。每間教室的座位都是 M×N 的矩陣(不同教室的 M, N 可以不一樣)，而有的座位壞掉了不能坐。此外，為了避免學生作弊，如下圖，對任何一個學生而言，他的左方、左前方、右方、右前方都不可以有人坐。請問每間教室所能容納的學生數最多為何？
輸入說明
第一行有一個數字 T，代表學校有 T 間教室。接下來會有每個教室的資料，每筆資料會有在同一行兩個正整數 M, N，代表座位的配置是 M×N。接下來的 M 行，每行有 N 個字元，'.'代表那個座位是好的，而'x'則代表那個座位壞了。
輸出說明
對於每間教室，輸出"Case #X: Y", 其中 X 代表這是第幾間教室，而 Y 則代表這間教室能容納的學生數最大值。
範例輸入
#1
4 2 3 ... ... 2 3 x.x xxx 2 3 x.x x.x 10 10 ....x..... .......... .......... ..x....... .......... x...x.x... .........x ...x...... ........x. .x...x....
範例輸出
#1
Case #1: 4 Case #2: 1 Case #3: 2 Case #4: 46
測資資訊：
記憶體限制：
512
MB
不公開 測資點#0 (20%): 1.0s , <1M
不公開 測資點#1 (80%): 1.0s , <1M
不公開 測資點#0 (20%): 1.0s , <1M
不公開 測資點#1 (80%): 1.0s , <1M
提示 ：
Small dataset
1 ≤ m, n ≤ 10
Large dataset
1 ≤ m, n ≤ 80
標籤:
出處:
GCJ2008Round 3C
[管理者：
xavier13540
(柊 四千)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||