首页 > ACM题库 > HDU-杭电 > HDU 4064-Carcassonne-动态规划-[解题报告]HOJ
2015
04-16

HDU 4064-Carcassonne-动态规划-[解题报告]HOJ

Carcassonne

问题描述 :

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

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.
Aircraft

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?

输入:

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.

输出:

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.

样例输入:

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

样例输出:

Case 1: 4
Case 2: 1
Case 3: 1048576

hdu 4064 Carcassonne

网上说是插头dp,若菜表示不知道什么叫插头dp,T_T

题意: 给你一个12*12 个瓷砖,每个瓷砖正方形,每个边用C,F,R唯一标示,用这些瓷砖相邻的两条边要相同,每个瓷砖可以旋转,问可能构成满足条件的瓷砖的个数

思路: dp[row ] [  states ]   states 是三进制表示的,表示该层的放置情况,用dfs枚举,我只是用了一点优化,500ms+

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;
#define MOD  1000000007
#define MAX 531443
int dp[13][MAX];
char st[13][13][6];
bool same[13][13];
int n,m,Max,cur,row;

int change(char x)
{
    if (x=='R') return 1;
    if (x=='F') return 2;
    return 0;
}

void dfs(int col,ll sum,char prechar,int pre,int now)
{
    if(col==m)
    {
        if(row==0) dp[row][now]=(dp[row][now]+sum)%MOD;
        else dp[row][now]=(dp[row][now]+sum*dp[row-1][pre])%MOD;
        return;
    }
    if(same[row][col]) // 判断该处是四个边否相同,如果相同直接dfs 一次即可 
    {
        if(prechar=='#'||prechar==st[row][col][0])
           dfs(col+1,sum*4%MOD,st[row][col][0],pre*3+change(st[row][col][0]),now*3+change(st[row][col][0]));
        return;
    }
    for(int i=0; i<4; i++)
        if(prechar=='#'||prechar==st[row][col][i])
            dfs(col+1,sum,st[row][col][(i+2)%4],pre*3+change(st[row][col][(i+1)%4]),now*3+change(st[row][col][(i+3)%4]));
}

int main()
{
    int T,i,j;
    scanf("%d",&T);
    for(int ca=1; ca<=T; ca++)
    {
        scanf("%d%d",&n,&m);
        for (i=0; i<n; i++)
        for (j=0; j<m; j++)
            scanf("%s",st[i][j]);
        memset(same,0,sizeof(same));
        Max=1;
        for (i=0; i<m; i++) Max*=3;
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            bool ok=1;
            for(int r=1;r<4;r++)
              if(st[i][j][r]!=st[i][j][r-1]) ok=0;
            same[i][j]=ok;
        }
        memset(dp,0,sizeof(dp));
        for(row=0;row<n;row++) dfs(0,1,'#',0,0);

        int ans=0;
        for(i=0;i<Max;i++) ans=(ans+dp[n-1][i])%MOD;
        printf("Case %d: %d\n",ca,ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/struggle_mind/article/details/8003221


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!