d664: 11725 - Colorful Board
Tags :
Accepted rate : 29人/36人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-03-23 14:39

Content

     給你一個板子,在上面M條水平線跟N條垂直線,因此在整個板子有(M+1) x (N+1)格子,現在請你在每個格子上填上顏色,總共有4種顏色Red,Green,Blue,Orange。

    為了使板子更加漂亮,你必須小心一件事情,兩鄰的格子不能有相同的顏色(相鄰的定義是有共同的邊),但是有些格子是被禁止塗上任何顏色的,題目來了,你必須回答有幾種方式可以塗完,但不觸犯以上規則。

Input

     第一個數字T(T<=50)代表有幾組冊資,每一組測資會給兩格數字M,N(0<M,N<=6)代表有幾條水平線跟垂直線,下一行但表有幾格被禁止不能圖畫的個數K(0<=K<=(M+1)*(N+1) ),接下來K行會包含兩個數字X,Y (1<=x<=M+1, 1<=y<=N+1),代表第X行的第Y個是被禁止塗畫。

Output

     對於每一個測資,請輸出一行 "Case #K: P",K代表第幾組測試資料,P代表有幾種可能,由於答案可能很大,請mod 1000000007

Sample Input
2
1 1
1
2 1
0 0
0
Sample Output
Case 1: 36
Case 2: 4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1K
Hint :
Tags:
出處:
UVa11725 [管理者:
snail (蝸牛)
]


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