CFR 611 C. New Year and Domino ( DP )

Problem - 611C - Codeforces
題意：
給一張有一些格子有障礙物的圖，接著多組詢問，用左上和右下座標描述。對於每筆詢問輸出該塊在原圖中，有多少種可以放 1 * 2 的條狀物的方法。
解法：
做二維前綴和，回答時再進一步刪去跨邊界的條狀物數量。
dp[ i ][ j ] : 考慮 行 [ 1, i ], 列 [ 1, j ] 構成的子圖，可以放置多少條狀物。
但是，如果只利用一般的排容處理，會忽略減去在不需要計算的塊和需要計算的塊之間的邊界形成橋樑的條狀物的數量。因此這部分要做額外的處理。

int N, M;
vs _G;

void init(){
	cin >> N >> M;
	_G.resize( N );
	for( int i = 0; i < N; ++i )
		cin >> _G[ i ];
}

vvi G;
vvi dp;
vvi row_cnt; // row_cnt[ i ][ j ] : number of tiles that can be put between row[ i ][ 1 .. j ] and row[ i - 1 ][ 1 .. j ]
vvi col_cnt;

void preprocess(){
	G = vvi( N + 1, vi( M + 1 ) );
	for( int i = 0; i < N; ++i )
		for( int j = 0; j < M; ++j )
			G[ i + 1 ][ j + 1 ] = _G[ i ][ j ] == '.';
	dp = vvi( N + 1, vi( M + 1 ) );
	for( int i = 1; i <= N; ++i )
		for( int j = 1; j <= M; ++j )
			dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1 ] - dp[ i - 1 ][ j - 1 ]
						 + ( G[ i - 1 ][ j ] & G[ i ][ j ] )
						 + ( G[ i ][ j - 1 ] & G[ i ][ j ] );
	row_cnt = vvi( N + 1, vi( M + 1 ) );
	for( int i = 1; i <= N; ++i )
		for( int j = 1; j <= M; ++j )
			row_cnt[ i ][ j ] = row_cnt[ i ][ j - 1 ] + ( G[ i - 1 ][ j ] & G[ i ][ j ] );
	col_cnt = vvi( M + 1, vi( N + 1 ) );
	for( int i = 1; i <= M; ++i )
		for( int j = 1; j <= N; ++j )
			col_cnt[ i ][ j ] = col_cnt[ i ][ j - 1 ] + ( G[ j ][ i - 1 ] & G[ j ][ i ] );
}

void solve(){
	int Q; cin >> Q;
	for( int i = 0; i < Q; ++i ){
		int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
		int ans = dp[ r2 ][ c2 ] - dp[ r2 ][ c1 - 1 ] - dp[ r1 - 1 ][ c2 ] + dp[ r1 - 1 ][ c1 - 1 ];
		ans -= col_cnt[ c1 ][ r2 ] - col_cnt[ c1 ][ r1 - 1 ];
		ans -= row_cnt[ r1 ][ c2 ] - row_cnt[ r1 ][ c1 - 1 ];
		cout << ans << endl;
	}
}