Discovering Paths (UVA 13050) by beet1333
Contest: 3738    RunID: 20173809    Status: Accepted    Date: Sat Oct 14 14:31:59 JST 2017


#include<bits/stdc++.h>

using namespace std;

const int mod = 912;

struct BeetAizu
{

  BeetAizu()
  {
  }

  void run()
  {
    int R, C, Q;
    cin >> R >> C >> Q;

    int dp1[1000][1000] = {{}}, dp2[1000][1000] = {{}};
    dp1[0][0] = 1;
    dp2[R - 1][C - 1] = 1;
    for(int i = 0; i < R; i++) {
      for(int j = 0; j < C; j++) {
        if(i) dp1[i][j] += dp1[i - 1][j];
        if(j) dp1[i][j] += dp1[i][j - 1];
        dp1[i][j] %= mod;
      }
    }
    for(int i = R - 1; i >= 0; i--) {
      for(int j = C - 1; j >= 0; j--) {
        if(i != R - 1) dp2[i][j] += dp2[i + 1][j];
        if(j != C - 1) dp2[i][j] += dp2[i][j + 1];
        dp2[i][j] %= mod;
      }
    }

    for(int i = 0; i < Q; i++) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;

      int ret = 0;
      {
        int x = c + 1, y = b - 1;
        while(x < R && y >= 0) {
          ret += dp1[x][y] * dp2[x][y];
          ret %= mod;
          ++x;
          --y;
        }
      }

      {
        int x = a - 1, y = d + 1;
        while(x >= 0 && y < C) {
          ret += dp1[x][y] * dp2[x][y];
          ret %= mod;
          --x;
          ++y;
        }
      }

      cout << "   Query " << i + 1 << ": ";
      cout << ret << endl;
    }
  }
};

int main()
{
  BeetAizu beet;
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++) {
    cout << "Case " << i << endl;
    beet.run();
  }
}