Discovering Paths (UVA 13050) by shot
Contest: 3738    RunID: 20184409    Status: Accepted    Date: Mon Oct 16 14:33:38 JST 2017


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

#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define Rep(i, n) for( int i = 0; i < (n); i++ )
#define Rrep(i, a, n) for( int i = (a); i < (n); i++ )
#define All(v) v.begin(), v.end()

typedef pair<int, int> Pii;
typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;
const int MOD = 912;

int dp[1001][1001];

signed main() {
    int T;
    cin >> T;

    for ( int id = 1; id <= T; id++ ) {
        cout << "Case " << id << endl;
        int R, C, Q;
        cin >> R >> C >> Q;
        memset(dp, 0, sizeof(dp));

        dp[C-1][R-1] = 1;
        for ( int i = C-1; i >= 0; i-- ) {
            for ( int j = R-1; j >= 0; j-- ) {
                if ( i < C-1 ) dp[i][j] += dp[i+1][j];
                if ( j < R-1 ) dp[i][j] += dp[i][j+1];
                dp[i][j] %= MOD;
            }
        }

        /*Rep(i, C) {
            Rep(j, R) printf("%5d", dp[i][j]);
            cout << endl;
        }*/

        for ( int q = 1; q <= Q; q++ ) {
            cout << "   Query " << q << ": ";
            int a, b, c, d;
            cin >> a >> b >> c >> d;

            int ans = 0;
            int x = c+1, y = b-1;
            while ( x < R && y >= 0 ) {
                ans += dp[y][x] * dp[C-y-1][R-x-1];
                x++; y--;
            }
            x = a-1; y = d+1;
            while ( y < C && x >= 0 ) {
                ans += dp[y][x] * dp[C-y-1][R-x-1];
                x--; y++;
            }

            cout << ans % MOD << endl;
        }
    }

    return 0;
}