C. New Year and Domino

dp, partial sum

출처: Codeforces C. New Year and Domino

SOL)
부분합을 구해야하는건 당연한데
생각을 해줘야할 부분이 (r2, c2) - (r1-1, c2)를 빼줄때
r1에 추가적으로 더 빼줘야 하는게 생긴다.
r1-1에 있는 빈공간을 이용해서 수직방향으로 만들었던
공간들도 빼줘야한다. (수평도 마찬가지)
수직 수평을 하나의 테이블로 관리하면 힘들다.
따라서 hor, ver로 따로 나눠서 계산을 해준다.


[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

const double pi = acos(-1);
const int N = 1000;

int hor[N][N], ver[N][N];
char board[N][N];
int h, w;
int n;

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d %d", &h, &w);

    for (int i = 1; i <= h; i++){
        scanf("%s", board[i] + 1);
    }

    for (int i = 1; i <= h; i++){
        for (int j = 1; j <= w; j++){
            hor[i][j] = hor[i - 1][j] + hor[i][j - 1] - hor[i - 1][j - 1];
            ver[i][j] = ver[i - 1][j] + ver[i][j - 1] - ver[i - 1][j - 1];

            if (board[i][j] == '.' && board[i][j - 1] == '.')
                hor[i][j]++;
            if (board[i][j] == '.' && board[i - 1][j] == '.')
                ver[i][j]++;
        }
    }

    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        int r1, c1, r2, c2;
        scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
        int ans = 0;
        ans += hor[r2][c2] - hor[r2][c1] - hor[r1 - 1][c2] + hor[r1 - 1][c1];
        ans += ver[r2][c2] - ver[r2][c1 - 1] - ver[r1][c2] + ver[r1][c1 - 1];

        printf("%d\n", ans);
    }

    return 0;
}