首页 > 代码库 > HDU4064 Carcassonne(状态压缩DP)

HDU4064 Carcassonne(状态压缩DP)

2024-07-21 00:27:33   213人阅读

Carcassonne

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 804    Accepted Submission(s): 312


Problem Description
Carcassonne is a tile-based board game for two to five players.
Square tiles are printed by city segments,road segments and field segments. 

The rule of the game is to put the tiles alternately. Two tiles share one edge should exactly connect to each other, that is, city segments should be linked to city segments, road to road, and field to field. 

To simplify the problem, we only consider putting tiles:
Given n*m tiles. You can rotate each tile, but not flip top to bottom, and not change their order. 
How many ways could you rotate them to make them follow the rules mentioned above?
 

Input
The first line is a number T(1<=T<=50), represents the number of case. The next T blocks follow each indicates a case.
Each case starts with two number N,M(0<N,M<=12)
Then N*M lines follow,each line contains M four-character clockwise.
‘C‘ indicate City.
‘R‘ indicate Road.
‘F‘ indicate Field.
 

Output
For each case, output the number of ways mod 1,000,000,007.(as shown in the sample output)
 

Sample Input
3
1 1
RRRR
1 2
RRRF FCCC
8 8
FCFF RRFC FRCR FRFR RCCR FFCC RRFF CRFR
FRRC FRFR CCCR FCFC CRRC CRRR FRCR FRFR
RRCR FRRR CCCR FFFC RRFF RFCR CCFF FCCC
CFCF RRFF CRFR FFRR FRRF CCRR FFFC CRRF
CFRR FFFF FFFF RRFF RRRR RCRR FFCC RFRF
RRCF FRFR FRRR FRFR RCCR RCCC CFFC RFRF
CFCF FRFF RRFF FFFF CFFF CFFF FRFF RFRR
CCRR FCFC FCCC FCCC FFCC FCCF FFCC RFRF
 

Sample Output
Case 1: 4
Case 2: 1
Case 3: 1048576
 
题意：n*m个格子（n,m<=12），每个格子四个面，最多有三种颜色组成，每个格子可以旋转，并且要求相接触的两个面的颜色必须相同，问方案数大小。
思路：状态压缩即可解决，三进制表示三种颜色，注意一个小剪枝，就是颜色相同的时候。只转移一个状态，然后在计算最后结果的时候乘上4。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MOD =  1000000007;
const int maxm = 550000+10;
typedef long long LL;
struct Mat{
    int top,rgt,bot,lft;
    bool same;
    Mat(int top,int rgt,int bot,int lft):top(top),rgt(rgt),bot(bot),lft(lft){
        same = (top==rgt&&top==bot&&top==lft&&rgt==bot&&rgt==lft&&bot==lft);
    }
    Mat(){}
};
Mat mat[13][13][5];
LL dp[2][maxm];
LL mi_3[14];
int fmask;
int n,m;
void init(){
    scanf("%d%d",&n,&m);
    memset(dp,0,sizeof dp);
    fmask = 1;
    for(int i = 1; i <= m; i++){
        fmask *= 3;
    }
}
int getDir(char op){
    if(op=='C') return 0;
    if(op=='F') return 1;
    if(op=='R') return 2;
}
void Rotate(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            for(int k = 1; k <= 3; k++){
                mat[i][j][k].top = mat[i][j][k-1].lft;
                mat[i][j][k].rgt = mat[i][j][k-1].top;
                mat[i][j][k].bot = mat[i][j][k-1].rgt;
                mat[i][j][k].lft = mat[i][j][k-1].bot;
            }
        }
    }
}
int getDigit(int mask,int x){//得到三进制右边的第x位
    while(x--){
        mask /= 3;
    }
    return mask%3;
}
void input(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            string str;
            int num[4];
            cin >> str;
            for(int k = 0; k < 4; k++){
                num[k] = getDir(str[k]);
            }
            mat[i][j][0] = Mat(num[0],num[1],num[2],num[3]);
        }
    }
    Rotate();
}
void dfs(int row,int col ,int lastmask,int nowmask,int botmask,LL val,int cnt){
    if(col==m){
        for(int i = 0; i < cnt; i++) {
            val = (val*4)%MOD;
        }
        dp[0][botmask] = (dp[0][botmask]+val)%MOD;
        return;
    }
    int up = getDigit(lastmask,col);
    if(mat[row][col][0].same) {
        if((col==0||mat[row][col][0].lft==nowmask)&&(row==0||mat[row][col][0].top==up)) {
            botmask += mat[row][col][0].bot*mi_3[col];
            dfs(row,col+1,lastmask,mat[row][col][0].rgt,botmask,val,cnt+1);
            botmask -= mat[row][col][0].bot*mi_3[col];
        }
    }else {
        for(int i = 0; i < 4; i++){
            if((col==0||mat[row][col][i].lft==nowmask)&&(row==0||mat[row][col][i].top==up)){
                botmask += mat[row][col][i].bot*mi_3[col];
                dfs(row,col+1,lastmask,mat[row][col][i].rgt,botmask,val,cnt);
                botmask -= mat[row][col][i].bot*mi_3[col];
            }
        }
    }
}
void solve(){
    dfs(0,0,0,0,0,1,0);
    for(int i = 1; i < n; i++){
        for(int j = 0; j < fmask; j++){
            dp[1][j] = dp[0][j];
            dp[0][j] = 0;
        }
        for(int j = 0; j < fmask; j++){
            if(dp[1][j]){
                dfs(i,0,j,0,0,dp[1][j],0);
            }
        }
    }
    LL ans = 0;
    for(int i = 0; i < fmask; i++){
        ans = (ans+dp[0][i])%MOD;
    }
    printf("%I64d\n",ans);
}
void doit(){
    mi_3[0] = 1;
    for(int i = 1; i < 14; i++){
        mi_3[i] = mi_3[i-1]*3;
    }
}
int main(){
    int ncase,T=1;
    doit();
    cin >> ncase;
    while(ncase--){
        init();
        input();
        printf("Case %d: ",T++);
        solve();
    }
    return 0;
}


HDU4064 Carcassonne(状态压缩DP)


联系
我们