2011-09-16 06:58:24Morris
d664. 11725 - Colorful Board
d664. 11725 - Colorful Board
內容 ：
給你一個板子，在上面M條水平線跟N條垂直線，因此在整個板子有(M+1) x (N+1)格子，現在請你在每個格子上填上顏色，總共有4種顏色Red,Green,Blue,Orange。
為了使板子更加漂亮，你必須小心一件事情，兩鄰的格子不能有相同的顏色(相鄰的定義是有共同的邊)，但是有些格子是被禁止塗上任何顏色的，題目來了，你必須回答有幾種方式可以塗完，但不觸犯以上規則。
輸入說明
：
第一個數字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個是被禁止塗畫。
輸出說明
：
對於每一個測資，請輸出一行 "Case #K: P"，K代表第幾組測試資料，P代表有幾種可能，由於答案可能很大，請mod 1000000007
範例輸入 ：
2 1 1 1 2 1 0 0 0
範例輸出 ：
Case 1: 36 Case 2: 4
提示
：
出處
：
UVA 11725
(管理：snail)
作法 : DP
總共 5 種情況, 0 沒填 1~4 四種顏色, 每一行可以用一個五進制表示,
因此可以得到, 每一行的總狀態, 在依照相鄰不可同色, 進行狀態轉移,
作法 : DP
總共 5 種情況, 0 沒填 1~4 四種顏色, 每一行可以用一個五進制表示,
因此可以得到, 每一行的總狀態, 在依照相鄰不可同色, 進行狀態轉移,
/**********************************************************************************/
/* Problem: d664 "11725 - Colorful Board" from UVA 11725 */
/* Language: C (1695 Bytes) */
/* Result: AC(676ms, 1.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-15 16:16:05 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
void change(int n, char *s) {
if(n == 0) return;
change(n/5, s+1);
*s = n%5;
}
int Calu(int n, char *s) {
if(n == 0) return 0;
return Calu(n-1, s+1)*5+(*s);
}
main() {
int T, n, m, K, x, y, C = 1;
int map[8][8], s5[10] = {1};
int i, j, k, l;
for(i = 1; i < 10; i++)
s5[i] = s5[i-1]*5;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &m, &n);
scanf("%d", &K);
memset(map, 0, sizeof(map));
for(i = 0; i < K; i++) {
scanf("%d %d", &x, &y);
map[x][y] = 1;
}
m++, n++;
int last[78126], now[78126];
int state = s5[n]-1, tmp, now_state;
char CH[10];
memset(last, 0, sizeof(last));
last[0] = 1;
for(i = 0; i < m; i++) {
for(j = 1; j <= n; j++) {
for(k = 0; k <= state; k++) {
memset(CH, 0, sizeof(CH));
change(k, CH);
if(last[k] == 0) continue;
if(j != 1 && CH[j-2] == 0 && map[i+1][j-1] == 0) continue;
if(j != 1 && CH[j-2] != 0 && map[i+1][j-1] != 0) continue;
if(map[i+1][j]) {
CH[j-1] = 0;
now_state = Calu(n, CH);
now[now_state] = (now[now_state] + last[k])%1000000007;
} else {
for(l = 1; l <= 4; l++) {
if(CH[j-1] != l && (j == 1 || CH[j-2] != l)) {
tmp = CH[j-1], CH[j-1] = l;
now_state = Calu(n, CH);
now[now_state] = (now[now_state] + last[k])%1000000007;
CH[j-1] = tmp;
}
}
}
}
for(k = 0; k <= state; k++)
last[k] = now[k]%1000000007;
memset(now, 0, sizeof(now));
}
}
int Ans = 0;
for(i = 0; i <= state; i++)
Ans = (Ans+last[i])%1000000007;
printf("Case %d: %d\n", C++, Ans);
}
return 0;
}