Discovering Paths (UVA 13050) by aizu_e
Contest: 3738    RunID: 20174571    Status: Wrong answer    Date: Sat Oct 14 16:40: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];
	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];
	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];
	else ruic[j][i] = dp[j][i];
      }
    }
    /*for ( int i = 0; i < C; i++ ) {
      for ( int j = 0; j < R; j++ ) {
	printf("%6d", dp[i][j]);
      }
      cout << endl;
      }*/
    for ( int q = 1; q <= Q; q++ ) {
      int a, b, c, d;
      int ans = dp[0][0] + MOD * 100000;
      //cout << ans << endl;
      cin >> a >> b >> c >> d;
      if ( a ) {
	if ( b ) ans -= ruic[d][a] - ruic[b-1][a];
	else ans -= ruic[d][a];
      }
      // cout << ans << endl;
      if ( b ) {
	if ( a ) ans -= ruir[b][c] - ruir[b][a-1];
	else ans -= ruir[b][c];	
      }

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