# CFR 611 C. New Year and Domino ( DP )

Problem - 611C - Codeforces

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;
}
}
```