The King's Walk

#include<bits/stdc++.h>
using namespace std;

const int P = 5318008;

int T;
int n, a1, b1, a2, b2;
int dp[5010], pre[5010];

int f(int s, int a, int b) {
    memset(dp, 0, sizeof(dp));
    memset(pre, 0, sizeof(pre));
    dp[a] = 1;
    for (int i = 0; i < s; i++) {
        for (int j = 0; j < n; j++) {
            pre[j] = dp[j];
            if (j > 0) pre[j] += dp[j-1];
            if (j < n-1) pre[j] += dp[j+1];
        }
        for (int j = 0; j < n; j++)
            dp[j] = pre[j] % P;
    }
    return dp[b];
}

int main() {
    cin >> T;
    while (T--) {
        cin >> n >> a1 >> b1 >> a2 >> b2;
        if (abs(a2-a1) > abs(b2-b1))
            cout << f(abs(a2-a1), b2-1, b1-1) << endl;
        else 
            cout << f(abs(b2-b1), a2-1, a1-1) << endl; 
    }
    
    return 0;
}

Test 1

Verdict: ACCEPTED