The King's Walk

思路：走的步数是确定的，是横坐标、纵坐标只差较大的那个，然后就是用确定的步数走另一个坐标差这样的距离，每次可以不走，前进一步，后退一步，不超出地图范围即可

 1 #include <iostream>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn=1e4+10;
 6 const double inf=9999999999.9;
 7 const int mod=5318008;
 8 #define rep(i,first,second) for(int i=first;i<=second;i++)
 9 #define dep(i,first,second) for(int i=first;i>=second;i--)
10 #define erep(i,u) for(int i=head[u];~i;i=e[i].nxt)
11 
12 int dp[maxn],DP[maxn];
13 int x1,y,x2,y2,n;
14 
15 void solve(int m,int st,int ed){
16     memset(dp,0,sizeof(dp));
17     dp[st]=1;
18     rep(i,1,m){//枚举当前步数
19         rep(j,1,n){//当前位置
20             DP[j]=dp[j];
21             if( j>1 ) DP[j]+=dp[j-1];
22             if( j<n ) DP[j]+=dp[j+1];
23         }
24         rep(j,1,n){
25             dp[j]=DP[j]%mod;
26         }
27     }
28     printf("%d
",dp[ed]);
29 }
30 
31 int main()
32 {
33     int t;
34     scanf("%d",&t);
35     while( t-- ){
36         scanf("%d",&n);
37         scanf("%d%d%d%d",&x1,&y,&x2,&y2);
38         int xx=abs(x1-x2),yy=abs(y-y2);
39         if( xx>yy ) solve(xx,y,y2);
40         else solve(yy,x1,x2);
41     }
42     return 0;
43 }