백준 5549 행성 탐사 C++

https://www.acmicpc.net/problem/5549

문제

상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 행성에서 거주 할 수 있는 구역의 지도를 만들어 지구로 보냈다.

상근이가 보내온 지도는 가로 Ncm, 세로 Mcm 직사각형 모양이다. 지도는 1cm 크기의 정사각형으로 나누어져 있고, 각 구역의 지형이 알파벳으로 표시되어 있다. 지형은 정글, 바다, 얼음 중 하나이며, 정글은 J, 바다는 O, 얼음은 I로 표시되어 있다.

지구에 있는 정인이는 조사 대상 영역을 K개 만들었다. 이때, 각 영역에 정글, 바다, 얼음이 각각 몇 개씩 있는지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 지도의 크기 M과 N이 주어진다. (1 ≤ M, N ≤ 1000)

둘째 줄에 정인이가 만든 조사 대상 영역의 개수 K가 주어진다. (1 ≤ K ≤ 100000)

셋째 줄부터 M개 줄에는 상근이가 보낸 지도의 내용이 주어진다.

다음 K개 줄에는 조사 대상 영역의 정보가 주어진다. 정보는 네 정수 a b c d로 이루어져 있다. 구역은 직사각형 모양 이며, 왼쪽 위 모서리의 좌표가 (a, b) 오른쪽 아래 모서리의 좌표가 (c, d)이다.

---

출력

각 조사 대상 영역에 포함되어 있는 정글, 바다, 얼음의 수를 공백으로 구분해 한 줄에 한 정보씩 출력한다.

---

힌트

두 번째 조사 대상 영역에는 정글(J)이 3개, 바다(O)가 5개, 얼음(I)이 2개 있다.

 

2차원 누적합으로 I,J,O에 대해 각각 배열을 만들고 계산해주었습니다.

#include <iostream>
#include <algorithm>
using namespace std;
int n,m,k;

int map_J[1001][1001];
int map_I[1001][1001];
int map_O[1001][1001];

void init(){
    cin >> n >> m;
    cin >> k;
    
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            char c;
            cin >> c;
            if(c == 'J'){
                map_J[i][j] = 1;
            }
            else if(c == 'I'){
                map_I[i][j] = 1;
            }
            else if(c == 'O'){
                map_O[i][j] = 1;
            }
        }
    }
}

void psum_calculate_J(){
    
    int dp[1001][1001] = {0, };

    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] + map_J[i][j];
            map_J[i][j] = dp[i][j];
        }
    }
}

void psum_calculate_I(){
    int dp[1001][1001] = {0, };
    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] + map_I[i][j];
            map_I[i][j] = dp[i][j];
        }
    }
}

void psum_calculate_O(){
    int dp[1001][1001] = {0, };
    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] + map_O[i][j];
            map_O[i][j] = dp[i][j];
        }
    }
}

int main(void){
    init();
    psum_calculate_J();
    psum_calculate_I();
    psum_calculate_O();
    
    for(int i = 0;i<k;i++){
        int x,y,x2,y2;
        scanf("%d %d %d %d",&x,&y,&x2,&y2);
        int diff_J = map_J[x2][y2] - map_J[x2][y-1] - map_J[x-1][y2] + map_J[x-1][y-1];
        int diff_O = map_O[x2][y2] - map_O[x2][y-1] - map_O[x-1][y2] + map_O[x-1][y-1];
        int diff_I = map_I[x2][y2] - map_I[x2][y-1] - map_I[x-1][y2] + map_I[x-1][y-1];
        printf("%d %d %d \n",diff_J,diff_O,diff_I);
    }
}