首页 > ACM题库 > HDU-杭电 > hdu 2323 Honeycomb Walk-动态规划-[解题报告]C++
2014
01-05

hdu 2323 Honeycomb Walk-动态规划-[解题报告]C++

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[n][sta_r][sta_c]就是为每次要求的答案(sta_r,sta_c为假设的中心坐标,这里设定为sta_r=15,sta_c = 15);

  第一道真正意义的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;
}

解题转自:http://www.cnblogs.com/keep-fighting/archive/2011/03/29/1999042.html


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