[BOJ/Gold 4] 백준 5549 행성 탐사(C++)

문제 링크

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

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)이다.

출력

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

예제 입력 1

4 7
4
JIOJOIJ
IOJOIJO
JOIJOOI
OOJJIJO
3 5 4 7
2 2 3 6
2 2 2 2
1 1 4 7

예제 출력 1

1 3 2
3 5 2
0 1 0
10 11 7

힌트

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

알고리즘 분류

• 누적 합

풀이

2차원 배열의 누적 합을 총 3번 구한다.(정글, 바다, 얼음)

그리고 K번에 걸쳐서 왼쪽 위 지점이 (A, B)이고, 오른쪽 아래 지점이 (C, D)인 구간의 정글, 바다, 얼음의 개수를 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int N, M, K, A, B, C, D;
char MAP[MAX][MAX];
int Sum[3][MAX][MAX];

void Input() {
	cin >> N >> M;
	cin >> K;
	for (int i = 1; i <= N; i++) {
		string S;
		cin >> S;
		for (int j = 1; j <= M; j++) {
			MAP[i][j] = S[j - 1];
		}
	}
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (MAP[i][j] == 'J') {
				Sum[0][i][j] = Sum[0][i - 1][j] + Sum[0][i][j - 1] - Sum[0][i - 1][j - 1] + 1;
				Sum[1][i][j] = Sum[1][i - 1][j] + Sum[1][i][j - 1] - Sum[1][i - 1][j - 1];
				Sum[2][i][j] = Sum[2][i - 1][j] + Sum[2][i][j - 1] - Sum[2][i - 1][j - 1];
			}
			else if (MAP[i][j] == 'O') {
				Sum[0][i][j] = Sum[0][i - 1][j] + Sum[0][i][j - 1] - Sum[0][i - 1][j - 1];
				Sum[1][i][j] = Sum[1][i - 1][j] + Sum[1][i][j - 1] - Sum[1][i - 1][j - 1] + 1;
				Sum[2][i][j] = Sum[2][i - 1][j] + Sum[2][i][j - 1] - Sum[2][i - 1][j - 1];
			}
			else if (MAP[i][j] == 'I') {
				Sum[0][i][j] = Sum[0][i - 1][j] + Sum[0][i][j - 1] - Sum[0][i - 1][j - 1];
				Sum[1][i][j] = Sum[1][i - 1][j] + Sum[1][i][j - 1] - Sum[1][i - 1][j - 1];
				Sum[2][i][j] = Sum[2][i - 1][j] + Sum[2][i][j - 1] - Sum[2][i - 1][j - 1] + 1;
			}
		}
	}
}

void Find_Answer() {
	while (K--) {
		cin >> A >> B >> C >> D;
		int First = Sum[0][C][D] - Sum[0][C][B - 1] - Sum[0][A - 1][D] + Sum[0][A - 1][B - 1];
		int Second = Sum[1][C][D] - Sum[1][C][B - 1] - Sum[1][A - 1][D] + Sum[1][A - 1][B - 1];
		int Third = Sum[2][C][D] - Sum[2][C][B - 1] - Sum[2][A - 1][D] + Sum[2][A - 1][B - 1];
		cout << First << " " << Second << " " << Third << "\n";
	};
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}