[状压dp] hdu 4064 Carcassonne
HDU DP 状压
2023-09-14 09:10:20 时间
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4064
Carcassonne
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 857 Accepted Submission(s): 326
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.
![](http://acm.hdu.edu.cn/data/images/C348-1004-1.jpg)
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.
![](http://acm.hdu.edu.cn/data/images/C348-1004-2.jpg)
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?
Square tiles are printed by city segments,road segments and field segments.
![](http://acm.hdu.edu.cn/data/images/C348-1004-1.jpg)
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.
![](http://acm.hdu.edu.cn/data/images/C348-1004-2.jpg)
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.
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
Source
Recommend
lcy
题目意思:
每一个格子有四条边,每条边有一种颜色,求通过旋转格子,使相邻格子公共边颜色同样,总的种数。
解题思路:
状态压缩dp
格子不多仅仅有12个,对于每一行维护两种状态,上边的颜色状态up和下边的颜色状态dw,一行搜完后,用上一行的dw状态(也就是当前行的up状态)更新当前行的dw状态。
滚动数组处理。
剪枝:当一个格子四边都是一样颜色的话直接*4,不用再枚举那一条边在上面
代码:
//#include<CSpreadSheet.h> #include<iostream> #include<cmath> #include<cstdio> #include<sstream> #include<cstdlib> #include<string> #include<string.h> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #include<bitset> #include<cmath> #define eps 1e-6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define ll __int64 #define LL long long #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #define M 1000000007 //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 15 char sa[Maxn][Maxn][5]; ll dp[2][1100000]; int ba[Maxn],n,m,cur,mul; map<char,int>myp; void dfs(int r,int nu,int up,int dw,int ri) { if(nu>m) { if(r==1) { dp[cur][dw]+=mul; dp[cur][dw]%=M; } else { dp[cur][dw]+=(dp[cur^1][up]*mul)%M; dp[cur][dw]%=M; } return ; } int i; for(i=1;i<4;i++) if(sa[r][nu][i]!=sa[r][nu][0]) break; if(i==4) //四个面都同样 { mul*=4; int a=myp[sa[r][nu][0]]; if(ri==-1||a==ri) dfs(r,nu+1,up*3+a,dw*3+a,a); mul/=4; return ; } for(int i=0;i<4;i++) { int uu=myp[sa[r][nu][i]]; int rr=myp[sa[r][nu][(i+1)%4]]; int dd=myp[sa[r][nu][(i+2)%4]]; int L=myp[sa[r][nu][(i+3)%4]]; if(ri==-1||L==ri) dfs(r,nu+1,up*3+uu,dw*3+dd,rr); } } int main() { //cout<<pow(3.0,12.0); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t,cas=0; myp['F']=0; myp['R']=1; myp['C']=2; ba[0]=1; for(int i=1;i<=12;i++) ba[i]=ba[i-1]*3; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%s",sa[i][j]); memset(dp,0,sizeof(dp)); cur=0; for(int i=1;i<=n;i++) { cur=cur^1; mul=1; dfs(i,1,0,0,-1); for(int j=0;j<ba[m];j++) dp[cur^1][j]=0; } ll ans=0; for(int i=0;i<ba[m];i++) { ans+=dp[cur][i]; ans%=M; } printf("Case %d: %d\n",++cas,ans); } return 0; }
相关文章
- HDU 1556-差分数组和线段树的对比分析-Color the ball
- hdu 3980 Paint Chain(SG函数)
- HDU 3336 KMP算法中对next数组的理解「建议收藏」
- HDU P3341 Lost’s revenge 题解+数据生成器
- hdu 3336 Count the string(kmp应用)
- hdu 3336 Count the string 用心写的题解
- 插头DP小结_dp插头接线标准
- hdu 1142_hdu1001
- HDU 3336 Count the string 解题报告
- [ACM] HDU 1006 解题报告
- H - Partial Tree HDU - 5534 【 完全背包 】
- HDU-2084 数塔
- 敌兵布阵(HDU 1166)
- I Hate It (HDU 1754)
- 校庆神秘建筑(HDU 1411)
- 还是畅通工程(HDU 1233)
- Friend-Graph (HDU 6152)2017中国大学生程序设计竞赛 - 网络选拔赛
- CaoHaha's staff (HDU 6154)(2017中国大学生程序设计竞赛 - 网络选拔赛)
- Oil Deposits (HDU - 1241 )(DFS思路 或者 BFS思路)
- 畅通工程续(HDU 1874)(简单最短路)
- Drainage Ditches (HDU - 1532)(最大流)
- Ancient Go ( HDU - 5546 ) ( BFS 搜索是否相连)
- 统计难题 【 HDU - 1251 】【 字典树 】
- Phone List 【 HDU - 1671 】 【 字典树判断是否存在前缀 】
- A * B Problem Plus【HDU 1402】 【FFT求高精度乘法】
- Bone Collector HDU - 2602【 01 背包 】
- 数据库恢复oracle数据库的DP技术实践(dp恢复oracle)
- 深入探索DP文件与Oracle的关系(dp 文件 oracle)
- 优雅编程从DP和Oracle开始(dp oracle)
- Oracle DP文件技术实现快速上手(oracle dp文件)