【网格图.题解】

思路

对于图表类问题，给多少信息就直接放在 DP 维度中就好了，由于题目中新填了一个限制，所以对于当前的位置 来说，可能需要知道上一次转移的具体信息，所以在开一维度记录有那个方向的数转移而来

表示 到 且是由 的方向转移而来的方案数，那么答案就是

对于 我们有五中状态，分别对应 上下左右，以及停留。

转移过程，考虑转移到他的那个对象是否是在距离 中的，如果在范围内，那么他会有两种选择

• 保持和当前的转移方向一致（题目给的
• 变成停留状态

分别对应的状态为 f[i-1][rx][ry][d],f[i-1][rx][ry][4] 这里 表示停留的意思，这些变量都可以在代码中看到，所以方便理解。

对于对象不在范围内的，他可以有任意状态转移而来。

然后这个题目就这样做完了。

值得注意的是

看起来很简单，但是我做了很久，题解都看不懂，只好自力更生，我在一些地方被卡这里点出

• 滚动数组优化
• 多次取模可能会 T
• 开long long + 多次取模会 T
• 不开 long long，看你是否有 (s%mod+a%mod+mod)%mod 他会爆 ，like 1500000000+1e9 然后 boom！

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int B=200+10;
const int mod=1e9+7;
int read() {int x;scanf("%d",&x);return x;}
int n,m,t;
int f[2][B][B][5];
int res[B][B][5];
int dx[5]={-1,1,0,0,0};
int dy[5]={0,0,1,-1,0};
int x1,x2,y1,y2;
int D;
int main()
{
    n=read(),m=read(),t=read(),x1=read(),y1=read(),D=read(),x2=read(),y2=read();
    f[0][1][1][4]=1;
    int now=0;
    for (int i=1;i<=t;i++)
    {
        now^=1;
        for (int x=1;x<=n;x++)
        {
            for (int y=1;y<=m;y++)
            {
                for (int d=0;d<=4;d++)
                {
                    int rx=x+dx[d],ry=y+dy[d]; 
                    if (rx>n || rx<1 || ry>m || ry<1) continue;
                    int sum=0;
                    if (max(abs(x1-rx),abs(y1-ry))<=D)//在范围内 
                    {    
                        if (d==4)//他可以有任何转台转移 
                        {
                            for (int l=0;l<=4;l++)
                            {
                                sum=(1ll*sum+f[now^1][rx][ry][l])%mod;
                            }
                        }
                        else 
                        {
                            sum=(1ll*sum+f[now^1][rx][ry][d])%mod;
                            sum=(1ll*sum+f[now^1][rx][ry][4])%mod;
                        }
                    }
                    else 
                    {
                        for (int l=0;l<=4;l++)
                        {
                            sum=(1ll*sum+f[now^1][rx][ry][l])%mod;
                        } 
                    }
                    f[now][x][y][d]=sum%mod;
                }
            }
        }
    }
    int ans=0;
    for (int i=0;i<=4;i++)
    {
        ans=(1ll*ans+f[now][x2][y2][i])%mod;
    }
    cout<<ans<<endl;

}
/*
3 1 5 999 999 1 2 1 
*/