[BOJ/백준] 30508 - 고인물이싫어

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

---

BFS를 통한 물이 고이지 않은 곳과 고인 곳을 분리하기

---

---

• 제목

고인물이싫어

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

비 오는 날 세종이는 부모님의 심부름으로 물을 사러 갔다. 횡단보도 앞에서 신호를 기다리던 세종이는 횡단보도가 평평하지 않아 물이 고인 것을 보았다. 횡단보도는 N X M 크기의 직사각형 격자 모양이며, 세종이가 서 있는 쪽 맨 앞의 맨 왼쪽 칸을 1행 1열, 맨 오른쪽 칸을 1행 M열로 부른다.

횡단보도 중 K개의 칸에는 하수구가 있다. 모든 칸은 상하좌우로 인접한 칸 중 높이가 자신보다 낮거나 같은 칸에 하수구나 물이 빠진 칸이 있으면 물이 빠진다. 하수구가 없는 칸 중 물이 빠지지 않은 칸을 물이 고인 칸이라고 한다. A+B를 풀고 받은 새 신발을 더럽히고 싶지 않았던 세종이는 물이 고인 칸을 밟지 않고 횡단보도를 건너려 한다. 세종이의 새 신발은 횡단보도의 연속된 h개의 행과 w개의 열을 덮는 크기의 직사각형 모양이다. 세종이는 횡단보도를 건널 때 항상 신발이 횡단보도의 격자 칸에 꼭 맞게 들어가게 발을 딛으며, 발의 방향을 돌리지 않는다.

횡단보도의 각 칸의 높이가 주어졌을 때, 세종이가 횡단보도에 신발을 더럽히지 않고 한쪽 발을 딛는 방법의 수를 구하는 프로그램을 작성하시오.

---

• 입력

첫째 줄에 횡단보도의 크기를 나타내는 두 정수 N,M이 공백으로 구분되어 주어진다. (1 ≤ N,M ≤ 1000)

둘째 줄에 세종이의 신발의 길이와 너비를 나타내는 두 정수 h,w가 공백으로 구분되어 주어진다. (1 ≤ h ≤ N; 1 ≤ w ≤ M)

그다음 N개의 줄에 걸쳐, i+2번째 줄에 M개의 정수 H[i][1] ,H[i][2] , ... ,H[i][M]이 공백으로 구분되어 주어진다. 이때 H[i][j]는 횡단보도의 i행 j열에 해당하는 칸의 높이를 의미한다. (1 ≤ H[i][j] ≤ 100)
 
N+3번째 줄에 하수구의 수를 나타내는 정수 K가 주어진다. (1 ≤ K ≤ N X M)

그다음 K개의 줄에 걸쳐 하수구의 위치를 나타내는 두 정수 r,c가 공백으로 구분되어 주어진다. 이는 횡단보도의 r행 c열에 하수구가 있음을 의미한다. 입력으로 주어지는 위치는 중복되지 않는다. (1 ≤ r ≤ N; 1 ≤ c ≤ M)

---

• 출력

첫째 줄에 세종이가 횡단보도에 한쪽 발을 딛는 방법의 수를 출력한다.

---

예제 입력1	예제 출력1
5 5 2 1 2 6 7 8 8 2 3 3 7 9 4 5 2 6 5 3 2 1 3 4 5 7 9 8 1 2 2 2 5 5	9

---

import java.io.*;
import java.util.*;

import javax.swing.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());

		int[][] road = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				road[i][j] = Integer.parseInt(st.nextToken()) - 1;
			}
		}

		boolean[][] safe = new boolean[N][M];
		Queue<Integer> queue = new ArrayDeque<>();
		int K = Integer.parseInt(br.readLine());
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			queue.add(x * M + y);
			safe[x][y] = true;
		}

		int[] dx = {1, -1, 0, 0};
		int[] dy = {0, 0, 1, -1};
		while (!queue.isEmpty()) {
			int curr = queue.poll();
			int x = curr / M;
			int y = curr % M;
			for (int k = 0; k < 4; k++) {
				int tx = x + dx[k];
				int ty = y + dy[k];
				if (tx < 0 || ty < 0 || tx >= N || ty >= M) {
					continue;
				}
				if (safe[tx][ty]) {
					continue;
				}
				if (road[x][y] > road[tx][ty]) {
					continue;
				}
				safe[tx][ty] = true;
				queue.add(tx * M + ty);
			}
		}
		int answer = 0;
		for (int i = 0; i <= N - H; i++) {
			for (int j = 0; j <= M - W; j++) {
				boolean able = true;
				for (int n = 0; n < H; n++) {
					for (int m = 0; m < W; m++) {
						if (!safe[i + n][j + m]) {
							able = false;
							break;
						}
					}
					if (!able) {
						break;
					}
				}
				if (able) {
					answer++;
				}
			}
		}
		System.out.println(answer);
	}
}