分析

对于一个节点从 恰好走 步走到 之类的都可以用 来处理。定义 代表第 步，到节点 ，当前方向是 的总方案数。那么一个节点可以从 个方向转移过来，再枚举自己的方向。时间复杂度为 。还有第一维可以用滚动数组优化空间。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 210,mod = 1e9 + 7;
int dx[5] = {0,0,0,1,-1},dy[5] = {0,1,-1,0,0};
int f[N][N][5],res[N][N][5],n,m,t,X1,X2,Y1,Y2,dis;
int main()
{
    cin >> n >> m >> t >> X1 >> Y1 >> dis >> X2 >> Y2;
    f[1][1][0] = 1;
    for(int T = 1;T <= t;T++) {
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                for(int k = 0;k < 5;k++)
                res[i][j][k] = f[i][j][k],f[i][j][k] = 0;
            }
        }
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                for(int last = 0;last < 5;last++) {
                    for(int k = 0;k < 5;k++)
                    {
                        int X = i + dx[k],Y = j + dy[k];
                        if(X < 1||Y < 1||X > n||Y > m) continue;
                        int check = max(abs(i-X1),abs(j-Y1));
                        if(check <= dis && last != k && last != 0 && k != 0) continue;
                        f[X][Y][k] = (f[X][Y][k] + res[i][j][last]) % mod; 
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i < 5;i++) ans = (ans + f[X2][Y2][i]) % mod;
    cout << ans << endl;
    return 0;
}