#35812: 先想過再進來


samlin961112@gmail.com (林哲甫)

School : 新北市私立南山高級中學
ID : 220506
IP address : [219.70.213.92]
Last Login :
2024-02-22 23:53:32
a228. 就少一個插座用很不方便 -- 2008 “Sunline Cup” National Invitational Contest | From: [219.70.213.92] | Post Date : 2023-06-17 22:19

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
 
int t, n, m, g[12][12], dp[12][12][1<<12], mod = 1e9+7;
 
int main(){
    cin >> t;
    for (int Case = 1; Case <= t; Case++){
        cin >> n >> m;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                cin >> g[i][j];
            }
        }
        memset(dp, 0, sizeof(dp));
        dp[0][m][0] = 1;

        // 使用動態規劃計算狀態
        for (int i = 1; i <= n; i++){
            for (int j = 0; j < (1<<m); j++){
                dp[i][0][j<<1] = dp[i-1][m][j];
            }
            for (int j = 1; j <= m; j++){
                int x = (1<<(j-1)); // 第 j 個位元為 1,代表蛇的身體的一部分
                int y = (1<<j); // 第 j+1 個位元為 1,代表蛇的身體的另一部分
                if (g[i][j] == 0){
                    // 如果是插座位置,不放置蛇
                    for (int s = 0; s < (1<<(m+1)); s++){
                        if ((s&x) || (s&y)){
                            // 如果 s 的第 j 或第 j+1 個位元為 1,表示插座位置已被蛇佔據
                            dp[i][j][s] = 0;
                        }
                        else dp[i][j][s] = dp[i][j-1][s]; // 否則,狀態與上一列同一行的相同
                    }
                }
                else{
                    // 如果是非插座位置,放置蛇
                    for (int s = 0; s < (1<<(m+1)); s++){
                        dp[i][j][s] = dp[i][j-1][s^x^y]; // 佔據插座位置的狀態
                        if (!!(s&x) != !!(s&y)) dp[i][j][s] += dp[i][j-1][s]; // 若 s 的第 j 和第 j+1 個位元只有一個為 1,則可以放置蛇
                        dp[i][j][s] %= mod; 
                    }
                }
            }
        }
        cout << "Case " << Case << ": " << dp[n][m][0] << "\n";
    }
}

 
ZeroJudge Forum