HDU 4064 Carcassonne(プラグDP)(The 36 th ACM/IPCC Asia Regional Fuzhou Site-Online Contest)
17426 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4064
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(0Then 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)
n*mの行列をあげて、各格子は1つのブロックがあって、ブロックの時計回りの方向の各辺の色を与えて、ブロックは回転することができて、隣接する辺の色が同じであることを要求して、何種類の方案がありますかを聞きます.
考え方:色で状態を作り、3色、4進数で.普通のプラグDPで、長い間プラグDPを書いていなかったので、結果は半日T_を調整しました.T.
コード(15 MS):
View Code
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
'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)
n*mの行列をあげて、各格子は1つのブロックがあって、ブロックの時計回りの方向の各辺の色を与えて、ブロックは回転することができて、隣接する辺の色が同じであることを要求して、何種類の方案がありますかを聞きます.
考え方:色で状態を作り、3色、4進数で.普通のプラグDPで、長い間プラグDPを書いていなかったので、結果は半日T_を調整しました.T.
コード(15 MS):
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 using namespace std;
6 typedef long long LL;
7
8 const int MAXN = 13;
9 const int SIZE = 1000007;
10 const int MOD = 1e9 + 7;
11
12 struct Hashmap {
13 int head[SIZE], ecnt;
14 int to[SIZE], next[SIZE], val[SIZE];
15 int stk[SIZE], top;
16
17 Hashmap() {
18 memset(head, -1, sizeof(head));
19 }
20
21 void clear() {
22 while(top) head[stk[--top]] = -1;
23 ecnt = 0;
24 //for(int i = 0; i < SIZE; ++i) if(head[i] != -1) cout<<"error"<<endl;
25 }
26
27 void insert(int st, int value) {
28 int h = st % SIZE;
29 for(int p = head[h]; ~p; p = next[p]) {
30 if(to[p] == st) {
31 val[p] += value;
32 if(val[p] >= MOD) val[p] -= MOD;
33 return ;
34 }
35 }
36 if(head[h] == -1) stk[top++] = h;
37 to[ecnt] = st; val[ecnt] = value; next[ecnt] = head[h]; head[h] = ecnt++;
38 }
39 } hashmap[2], *pre, *cur;
40
41 char s[MAXN][MAXN][5];
42 int w[128];
43 int n, m, T;
44
45 int getState(int state, int i) {
46 return (state >> (i << 1)) & 3;
47 }
48
49 void setState(int &state, int i, int val) {
50 i <<= 1;
51 state = (state & ~(3 << i)) | (val << i);
52 }
53
54 int solve() {
55 pre = &hashmap[0], cur = &hashmap[1];
56 cur->clear();
57 cur->insert(0, 1);
58 int maxState = (1 << ((m + 1) << 1)) - 1;
59 for(int i = 0; i < n; ++i) {
60 for(int p = 0; p < cur->ecnt; ++p)
61 cur->to[p] = (cur->to[p] << 2) & maxState;
62 for(int j = 0; j < m; ++j) {
63 swap(pre, cur);
64 cur->clear();
65 for(int p = 0; p < pre->ecnt; ++p) {
66 int st = pre->to[p];
67 for(int k = 0; k < 4; ++k) {
68 if(j != 0 && w[(int)s[i][j][(k + 1) & 3]] != getState(st, j)) continue;
69 if(i != 0 && w[(int)s[i][j][(k + 2) & 3]] != getState(st, j + 1)) continue;
70 int new_st = st;
71 setState(new_st, j, w[(int)s[i][j][k]]);
72 setState(new_st, j + 1, w[(int)s[i][j][(k + 3) & 3]]);
73 cur->insert(new_st, pre->val[p]);
74 }
75 }
76 }
77 }
78 int res = 0;
79 for(int p = 0; p < cur->ecnt; ++p) {
80 res += cur->val[p];
81 if(res >= MOD) res -= MOD;
82 }
83 return res;
84 }
85
86 int main() {
87 w['F'] = 0; w['C'] = 1; w['R'] = 2;
88 scanf("%d", &T);
89 for(int t = 1; t <= T; ++t) {
90 scanf("%d%d", &n, &m);
91 for(int i = 0; i < n; ++i)
92 for(int j = 0; j < m; ++j) scanf("%s", s[i][j]);
93 printf("Case %d: %d
", t, solve());
94 }
95 }View Code