1284. Honeycomb Walk

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

const int N = 60;
const int MOVES = 15;
const int INF = (int)1e18;

int dp[N][N][MOVES]={};

signed main()
{
    ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    dp[30][30][0]=1;

    for(int step=1;step<15;step++)
    {
        for(int x=15;x<=45;x++)
        {
            for(int y=15;y<=45;y++)
            {
                dp[x][y][step] = dp[x][y-1][step-1] + dp[x-1][y][step-1]
                               + dp[x-1][y-1][step-1] + dp[x][y+1][step-1]
                               + dp[x+1][y][step-1] + dp[x+1][y+1][step-1];
            }
        }
    }

    int t;
    cin >> t;

    while(t--)
    {
        int a;
        cin >> a;
        cout << dp[30][30][a] << "\n";
    }

    return 0;
}