5549 행성 탐사 - 백준

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

5549번: 행성 탐사

풀이

행성은 정글, 바다, 얼음이 뒤얽힌 행성

 

가로 N, 세로 M

정글: J, 바다: O, 얼음: I

조사대상 영역 K개

이 영역에 정글, 바다, 얼음이 몇개씩 있는지 구해야 함

 

입력

첫째 줄

M, N

둘째 줄

K

M개 줄

상근이가 보낸 지도 내용

K줄

조사 대상 영역의 정보 a, b, c, d 왼위, 오아 좌표

 

출력

각 조사 대상 영역에 포함된 정글, 바다, 얼음의 수를 공백으로 구분해 표시

 

시간복잡도 o(m*n*3)

코드

package test28217;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int M;
	static int K;

	static int[][][] map; // 정글, 바다, 얼음 3차원 배열

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);

		M = sc.nextInt();
		N = sc.nextInt();
		K = sc.nextInt();

		map = new int[M + 1][N + 1][3];
		for (int i = 0; i < M; i++) {
			char[] chars = sc.nextToken().toCharArray();
			for (int j = 0; j < N; j++) {
				switch (chars[j]) {
				case 'J':
					map[i + 1][j + 1][0] = 1;
					break;
				case 'O':
					map[i + 1][j + 1][1] = 1;
					break;
				case 'I':
					map[i + 1][j + 1][2] = 1;
					break;
				}
			}
		}
		for (int i = 1; i < M + 1; i++) {
			for (int j = 0; j < N + 1; j++) {
				for (int l = 0; l < 3; l++) {
					map[i][j][l] += map[i - 1][j][l];
				}
			}
		}

		for (int i = 0; i < M + 1; i++) {
			for (int j = 1; j < N + 1; j++) {
				for (int l = 0; l < 3; l++) {
					map[i][j][l] += map[i][j - 1][l];
				}
			}
		}
		/*
		 * for (int l = 0; l < 3; l++) { System.out.print("i = " + l + "//\n"); for (int
		 * i = 0; i < M + 1; i++) { for (int j = 0; j < N + 1; j++) {
		 * System.out.print(map[i][j][l] + " "); } System.out.println("\n");
		 * 
		 * } System.out.println("\n"); }
		 */

		for (int k = 0; k < K; k++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			int d = sc.nextInt();

			for (int i = 0; i < 3; i++) {
				sc.write(map[c][d][i] - map[a - 1][d][i] - map[c][b - 1][i] + map[a - 1][b - 1][i] + " ");
			}
			sc.write("\n");
		}

		sc.close();

	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		String nextLine() throws IOException {
			return reader.readLine();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void write(String sb) throws IOException {
			writer.write(sb);
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}