POJ 3036 Honeycomb Walk

http://poj.org/problem?id=3036

在每一个格子可以转移到与这个各自相邻的六个格子

那么设置转移变量只需要六个 int d[6][2] = {-1, 0, -1, 1, 0, 1, 1, 0, 1, -1, 0, -1};
然后设dp[i][j][k] : 第i步走到(j ,k) 的方式数

那么转移方程：

for (int m = 0; m < 6; m++)

dp[i][j][k] += dp[i-1][j+d[m][0]][k+d[m][1]]

三个维度的状态最后得到dp[n][O][O] 就是最后回到原点的个数六边形只需要坐标六个变化

因为最多n = 14

最多上下最多可以走14 / 2 = 7个

所以设置(7 , 7) 为原点

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define INF 0x3fffffff

 using namespace std;

 long long dp[][][];

 int d[][] = {-, , -, , , , , , , -, , -}; //开始坐标标错了

 int dx[]={,,,-,,-};

 int dy[]={,,,,-,-};

 int main()

 {

     memset(dp, , sizeof(dp));

     dp[][][] = ;

     for (int i = ; i <= ; i++)

         for(int j = ; j <= ; j++)

             for(int k = ; k <= ; k++)

                 for(int m = ; m < ; m++)

                     dp[i][j][k] += dp[i-][j+d[m][]][k+d[m][]];

     int T;

     cin >> T;

     while (T--)

     {

         int n;

         cin >> n;

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

     }

     return ;

 }

巴特西

POJ 3036 Honeycomb Walk

最新文章

热门文章