• 题目分析

    1. 我的第一个想法是bfs(QwQ),不用说，肯定凉凉。

    2. 思考，对于一个点( i , j )，如果和小B的切比雪夫距离大于D，那么肯定可以转移到 ( i , j )的四个方向，

      也可以停留原地。但是如果小于等于D时，肯定只能单方向转移或是停留原地

    3. 这样我们就可以写出dp方程了

      设f[ t ] [ dir ][ i ][ j ]为第 t 秒，上一次从 dir 方向走到了点( i , j ),这样是500* 5 * 200 * 200,采用滚动数组

      if(get(i,j)<=d)
         {//在范围内 
             for (int k=0;k<=4;k++)
             {//向四个方向扩展
                 if(k!=0) f[h][0][i][j]+=f[l][k][i][j];
                 f[h][0][i][j]%=mod;

                 int xx=dx[k]+i,yy=dy[k]+j;
                 if(check(xx,yy)) continue;
                 if(k!=0) f[h][k][xx][yy]+=f[l][k][i][j];
                 f[h][k][xx][yy]+=f[l][0][i][j];
                 f[h][k][xx][yy]%=mod;
             }/*
              根据题目要求，点只能从上一个方向走过来，于是枚举k，0表示停留
而若是停留，那么就可以加上从任意方向走到这个点的方案数，若是选择继续走，那
么就得走对应方向，但是注意0方向会重复，要判断一下k是否为0*/
         }

    4. 若是不在范围内，那就可以加上任意方向的方案数

      else
        {
        //如果不在范围内,那么一定可以从上一次的四个方向随意转移一个
            int tot=0;
            for (int k=0;k<=4;k++) tot+=f[l][k][i][j],f[l][k][i][j]=0,tot%=mod;
            for (int k=0;k<=4;k++)
            {
                int xx=i+dx[k],yy=j+dy[k];
                if(check(xx,yy)) continue;

                f[h][k][xx][yy]+=tot;
                f[h][k][xx][yy]%=mod;
            }
        }//反之，可以feel free，在范围内乱走

    5. 最后直接统计答案就行了

      int ans=0;
for (int k=0;k<=4;k++) ans+=f[t&1][k][zx][zy],ans%=mod;
printf("%d\n",ans);