a576: No Cheating
Tags :
Accepted rate : 18人/48人 ( 38% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-04-09 02:29

Content
有個學校想辦一場考試,提供了 T 間教室。每間教室的座位都是 M×N 的矩陣(不同教室的 M, N 可以不一樣),而有的座位壞掉了不能坐。此外,為了避免學生作弊,如下圖,對任何一個學生而言,他的左方、左前方、右方、右前方都不可以有人坐。請問每間教室所能容納的學生數最多為何? 
 
Input

第一行有一個數字 T,代表學校有 T 間教室。接下來會有每個教室的資料,每筆資料會有在同一行兩個正整數 M, N,代表座位的配置是 M×N。接下來的 M 行,每行有 N 個字元,'.'代表那個座位是好的,而'x'則代表那個座位壞了。 

Output

對於每間教室,輸出"Case #X: Y", 其中 X 代表這是第幾間教室,而 Y 則代表這間教室能容納的學生數最大值。

Sample Input #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....
Sample Output #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
Hint :

Small dataset

1 ≤ m, n ≤ 10

Large dataset

1 ≤ m, n ≤ 80

Tags:
出處:
GCJ2008Round 3C [管理者:
xavier13540 (柊 四千)
]


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