2014
01-05

# Honeycomb Walk

A bee larva living in a hexagonal cell of a large honeycomb decides to creep for a walk. In each “step” the larva may move into any of the six adjacent cells and after n steps, it is to end up in its original cell.
Your program has to compute, for a given n, the number of different such larva walks.

The first line contains an integer giving the number of test cases to follow. Each case consists of one line containing an integer n, where 1 ≤ n ≤ 14.

The first line contains an integer giving the number of test cases to follow. Each case consists of one line containing an integer n, where 1 ≤ n ≤ 14.

2
2
4

6
90

开始看到这道题知道要用dp,但这个六边形的确很恶心,每次坐标的偏移量无法用二维数组完整表现出来,后经过看多方题解，明白了可以取八个方向中的六个,解决了构图的问题，至于状态转移是很明显的。dp[s][i][j]表示经过s步到达坐标为[i][j]的位置的路径数:

则dp[s][i][j] = dp[s-1][i-1][j-1]+dp[s-1][i][j-1]+dp[s-1][i+1][j]+dp[s-1][i+1][j+1]+dp[s-1][i][j+1]+d[s-1][i-1][j];

第一道真正意义的dp，纪念一下O(∩_∩)O

#include <iostream>
#include <cstring>

using namespace std;
int dp[17][30][30],sta_r = 15,sta_c = 15;
int move[6][2] = {{-1,-1},{0,-1},{1,0},{1,1},{0,1},{-1,0}};

int main()
{
int t,n,i,r,c,k;

cin>>t;

memset(dp,0,sizeof(dp));
dp[0][sta_r][sta_c] = 1;

for(i = 1;i < 15;++i)
{
for(r = 0;r < 30;++r)
{
for(c = 0;c < 30;++c)
{
for(k = 0;k < 6;++k)
{
int cur_row = r + move[k][0];
int cur_col = c + move[k][1];
dp[i][r][c] += dp[i-1][cur_row][cur_col];
}
}
}
}

while(t--)
{
cin>>n;

cout<<dp[n][sta_r][sta_c]<<endl;

}

return 0;
}

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法