Discovering Paths (UVA 13050) by ynu_a
Contest: 3738    RunID: 20173890    Status: Time limit exceeded    Date: Sat Oct 14 14:43:16 JST 2017


#include<bits/stdc++.h>

// Shrotening
#define fst first
#define snd second
#define pb push_back

// Loop
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define RFOR(i,a,b) for(long i=(a);i>=(b);--i)

#define REP(i,a) FOR(i,0,a)
#define RREP(i,a) RFOR(i,a,0)

#define EACH(i,a) for(auto (i)=(a).begin(),_END=(a).end();i!=_END;++i)
#define REACH(i,a) for(auto (i)=(a).rbegin(),_END=(a).rend();i!=_END;++i)

//Algorithm
#define ALL(a) (a).begin(), a.end()
#define RALL(a) (a).rbegin(), a.rend()
#define EXIST(a,x) ((a).find(x)!=(a).end())
#define SORT(a) sort(ALL(a))

//Setting
#define OPT std::cin.tie(0);std::ios::sync_with_stdio(false);

//debug message
bool debug = true;
#define MSG(s)   if(debug){std::cout << s << std::endl;}
#define DEBUG(x) if(debug){std::cout << "debug(" << #x << "): " << x << std::endl;}

//alias
typedef long long LL;
typedef std::vector<int> VI;
typedef std::vector<long> VL;
typedef std::vector<long long> VLL;
typedef std::pair<int,int> PII;

int T;
int R, C, Q;
int a, b, c, d;

std::vector< std::vector<long> > base(1000, VL(1000));
std::vector< std::vector<long> > memo(1000, VL(1000));
void init() {
    RREP(i, C-1) {
        RREP(j, R-1) {
            if(i == C-1 || j == R-1) {
                base[i][j] = 1;
            } else {
                base[i][j] = base[i+1][j] + base[i][j+1];
            }
        }
    }
    base[C-1][R-1] = 0;
}

long long solve() {
    REP(i, C) {
        REP(j, R) {
            memo[i][j] = base[i][j];
        }
    }

    RREP(i, d) {
        RREP(j, c) {
            if(i == C-1 && j == R-1) {
                memo[i][j] = 0;
            } else if(i >= b && i <= d && j>=a && j<=c) {
                memo[i][j] = -1;
            } else {
                long a = memo[i+1][j];
                long b = memo[i][j+1];
                memo[i][j] = std::max(0l, a) + std::max(0l, b);
            }
        }
    }
    return memo[0][0];
}
int main() {
    std::cin >> T;
    REP(i, T) {
        std::cout << "Case " << i+1 << std::endl;

        std::cin >> R >> C >> Q;
        init();
        REP(j, Q) {
            std::cin >> a >> b >> c >> d;
            long long ans = solve();
            std::cout << "   Query " << j+1 << ": " << ans << std::endl;
        }
    }
}