Discovering Paths (UVA 13050) by aizu_e
Contest: 3738    RunID: 20174335    Status: Wrong answer    Date: Sat Oct 14 15:50:18 JST 2017


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

#define int long long
const int MOD = 912;

int dp[1001][1001] = {{0}};
int ruir[1001][1001] = {{0}};
int ruic[1001][1001] = {{0}};

signed main() {
  int T;
  cin >> T;
  for ( int id = 1; id <= T; id++ ) {
    cout << "Case " << id << endl;
    int R, C, Q;
    for ( int i = 0; i < 1001; i++ ) {
      for ( int j = 0; j < 1001; j++ ) {
	dp[i][j] = ruir[i][j] = ruic[i][j] = 0;
      }
    }
    cin >> R >> C >> Q;
    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], dp[i][j] %= MOD;
	if ( j < R-1 ) dp[i][j] += dp[i][j+1], dp[i][j] %= MOD;	
      }
    }
    for ( int i = 0; i < C; i++ ) {
      for ( int j = 0; j < R; j++ ) {
	if ( j ) ruir[i][j] = ruir[i][j-1] + dp[i][j], ruir[i][j] %= MOD;
	else ruir[i][j] = dp[i][j];
      }
    }
    for ( int i = 0; i < R; i++ ) {
      for ( int j = 0; j < C; j++ ) {
	if ( j ) ruic[j][i] = ruic[j-1][i] + dp[j][i], ruic[i][j] %= MOD;
	else ruic[j][i] = dp[j][i];
      }
    }
    /*for ( int i = 0; i < C; i++ ) {
      for ( int j = 0; j < R; j++ ) {
	cout << ruic[i][j] << " ";
      }
      cout << endl;
      }*/
    for ( int q = 1; q <= Q; q++ ) {
      int a, b, c, d;
      int ans = dp[0][0] + MOD + MOD;
      cin >> a >> b >> c >> d;
      if ( a ) {
	if ( b ) ans -= ruic[d][a] + MOD - ruic[b-1][a];
	else ans -= ruic[d][a];
      }
      if ( b ) {
	if ( a ) ans -= ruir[b][c] + MOD - ruir[b][a-1];
	else ans -= ruir[b][c];	
      }

      cout << "   Query " << q << ": ";
      if ( (a == 0 && b == 0) || (a == R-1 && b == C-1) ) cout << 0 << endl;
      else cout << ans % MOD << endl;
    }
  }
}