2015
04-16

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.

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?

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

#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;
}


1. 恩，没有什么不对，只是比较强势，所以本地的辣椒经销商不太高兴，而且贵州辣椒其实挺贵的。大家不太满意的其实是，本地人吃了老干妈很多年，能够明显的感觉到质量的下降

2. 恩，没有什么不对，只是比较强势，所以本地的辣椒经销商不太高兴，而且贵州辣椒其实挺贵的。大家不太满意的其实是，本地人吃了老干妈很多年，能够明显的感觉到质量的下降

3. 恩，没有什么不对，只是比较强势，所以本地的辣椒经销商不太高兴，而且贵州辣椒其实挺贵的。大家不太满意的其实是，本地人吃了老干妈很多年，能够明显的感觉到质量的下降

4. 恩，没有什么不对，只是比较强势，所以本地的辣椒经销商不太高兴，而且贵州辣椒其实挺贵的。大家不太满意的其实是，本地人吃了老干妈很多年，能够明显的感觉到质量的下降

5. 恩，没有什么不对，只是比较强势，所以本地的辣椒经销商不太高兴，而且贵州辣椒其实挺贵的。大家不太满意的其实是，本地人吃了老干妈很多年，能够明显的感觉到质量的下降

6. 恩，没有什么不对，只是比较强势，所以本地的辣椒经销商不太高兴，而且贵州辣椒其实挺贵的。大家不太满意的其实是，本地人吃了老干妈很多年，能够明显的感觉到质量的下降

7. 恩，没有什么不对，只是比较强势，所以本地的辣椒经销商不太高兴，而且贵州辣椒其实挺贵的。大家不太满意的其实是，本地人吃了老干妈很多年，能够明显的感觉到质量的下降

8. 漂亮。佩服。
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));
}
}

9. 在方法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的边不是都没了吗？

10. 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!