前几天打的一场比赛的E题

https://ac.nowcoder.com/acm/contest/30532/E

原题是要求输出最短步数，用bfs可以做。

改了一下，变为dp问题。设\(dp_{i,j,k}\)是到达点\((i,j)\)，花费\(k\)步的方案数，则有

\(dp_{i,j,k} = \sum dp_{i',j',k-1}\)，若\((i',j')\)能一步到达\((i,j)\)。

void solve()
{
    int n, m, a, b, c, d, k;
    cin>>n>>m>>a>>b>>c>>d>>k;
    
    auto ok = [&](int x, int y){
        return x<=n && x>0 && y<=m && y>0;
    };
    
    array<int,2> dir8[] = {
        {2, 1},
        {2, -1},
        {-2, 1},
        {-2, -1},
        {1, 2},
        {1, -2},
        {-1, 2},
        {-1, -2}
    };

    dp[a][b][0] = 1;
    for(int i=1;i<=k;i++)
    {
        for(int x=1;x<=n;x++)
        {
            for(int y=1;y<=m;y++)
            {
                for(auto _: dir8)
                {
                    int x1 = _[0] + x, y1 = _[1] + y;
                    if(ok(x1, y1))
                    {
                        dp[x1][y1][i] += dp[x][y][i-1];
                    } 
                }
            }
            
        }
    }
    Mint ans = 0;
    for(int i=1;i<=k;i++) ans += dp[c][d][i];
    cout<<ans<<'\n'; 
    //cout<<dp[c][d][k]<<'\n';
}