Discovering Paths (UVA 13050) by s1230151
Contest: 3738    RunID: 20184122    Status: Presentation error    Date: Mon Oct 16 13:08:28 JST 2017


#include<bits/stdc++.h>

using namespace std;


int main(){

  int T,m=912;
  cin>>T;
  for(int tt=1;tt<=T;tt++){
    int w,h,q;
    cin>>w>>h>>q;
    int dp[1001][1001]={};
    dp[0][0]=1;
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++){
	dp[i+1][j]=(dp[i+1][j]+dp[i][j])%m;
	dp[i][j+1]=(dp[i][j+1]+dp[i][j])%m;	
      }
    cout<<"Case "<<tt<<endl;

    for(int Q=1;Q<=q;Q++){
      int a,b,c,d;
      cin>>a>>b>>c>>d;
      a--,b--,c++,d++;
      int ans=0,t=0;
      for(int i=a;i>=0&&d+t<h;i--){
	ans=(ans+dp[d+t][i]*dp[h-(d+t)-1][w-i-1])%m;
	t++;
      }
      t=0;
      for(int i=c;i<w&&b-t>=0;i++){
	ans=(ans+dp[b-t][i]*dp[h-(b-t)-1][w-i-1])%m;
	t++;
      }
      cout<<"Query "<<Q<<": "<<ans<<endl;
    }    
  }
  return 0;
}