一眼感觉转移,但是状态炸了

然后想到线性,但没有明显的转移顺序

所以可以考虑把步数设进状态,这样最外层只需要循环即可转移

又因为转移牵涉到上一次的移动方向

所以设表示走了步,目前在位置,利用方向走到当前位置的

转移很显然了

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,m,dp[2][209][209][5],t,d,x1,x2,y11,y2;
char a[209][209];
int x[6]={0,0,0,1,-1};
int y[6]={0,1,-1,0,0};
signed main()
{
    cin >> n >> m >> t >> x1 >> y11 >> d >> x2 >> y2;
    dp[0][1][1][0]=1;
    for(int s=1;s<=t;s++)
    {
        memset(dp[s&1],0,sizeof(dp[s&1]));
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            for(int f=0;f<5;f++)//枚举自己的方向 
            {
                int nx=i-x[f],ny=j-y[f];//上一次位置的座标
                if( nx<1||ny<1||nx>n||ny>m )    continue; 
                int ok=0;
                if( max(abs(x1-nx),abs(y11-ny))<=d )    ok=1;
                for(int q=0;q<5;q++)//枚举上一次的方向 
                {
                    if( ok&&q&&f!=0&&f!=q )    continue;
                    dp[s&1][i][j][f]+=dp[(s&1)^1][nx][ny][q];
                    dp[s&1][i][j][f]%=mod;
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<5;i++)
        ans+=dp[t&1][x2][y2][i],ans%=mod;
    cout << ans;
}