a228: 就少一個插座用很不方便
Tags : DP
Accepted rate : 130人/143人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-14 11:56

Content

小P家裡養了很多隻蛇,他每天都會陪牠們玩。

怎麼玩呢? 他把家裡劃分成N*M的方格,接著把這些蛇擺上地板。

每個方格只能被一隻蛇的身體容納,所以每隻蛇的位置都可以用一串連續方格表示。

這些蛇由於很害羞,所以他們都咬著自己的尾巴。也就是每隻蛇都形成一個環狀。

 

然而有些格子上有插座,如果一隻蛇佔據了有插座的格子,這樣就少一個插座用很不方便。

所以小P希望有插座的格子不能被蛇佔據。

而且小P也不希望沒有插座的格子上面是空的,也就是希望每個格子都被恰好一隻蛇佔據。

 

小P給了你他家地板的平面圖,他想問你總共有幾種放蛇的方法能符合上述條件。

因為方法數太多了,請輸出MOD 1000000007的結果

值得注意的是擺幾條蛇完全隨意,你可以一條都不擺或擺二三十條。

 

 

Input
輸入第一行包含測資筆數T,T<=50。

每筆測資第一行有兩個正整數1 <= N, M <= 11,表示小P家大小。

接下來有N行每行有M個0或1的數字,1表示該格為空、0表示該格有插座。
Output

對每筆輸出一行答案,格式如下:

Case(空格)(筆數編號,從1開始):(空格)(答案)

請不要輸出多餘的空白或換行。

 

Sample Input
3
6 3
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 1 1
2 4
1 1 1 1
1 1 1 1
1 1
0
Sample Output
Case 1: 3
Case 2: 2
Case 3: 1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :

請相信爆搜不會過。

 

第一筆範例的解釋:

Tags:
DP
出處:
2008 “Sunline Cup” National Invitational Contest [管理者:
poao899 (帥氣傳說勇士)
]


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