백준 14719 - 빗물

문제링크

• 백준 14719

문제설명

• 2차원 격자 위에 블록이 쌓여 있다.
• 비가 오면 블록 사이에 빗물이 고이는데, 고이는 빗물의 총량을 구하라.

문제접근

• 빗물이 고이기 위해서는 좌우에 블록이 있어야만 한다.
• 비어 있는 칸의 좌측, 우측을 탐색하여 양쪽에 블록이 모두 존재하는 경우 빗물 총량을 추가한다.

구현

#include <iostream>
#include <vector>
using namespace std;

int H, W;
int board[500][500];

bool checkLeft(int x, int y) {
	for (int c = y - 1; c >= 0; c--) {
		if (board[x][c] == 1) return true;
	}
	return false;
}

bool checkRight(int x, int y) {
	for (int c = y + 1; c < W; c++) {
		if (board[x][c] == 1) return true;
	}
	return false;
}

int getRain() {
	int ans = 0;

	for (int r = 0; r < H; r++) {
		for (int c = 0; c < W; c++) {
			if (board[r][c] == 1) continue;
			if (checkLeft(r, c) && checkRight(r, c)) ans++;
		}
	}
	return ans;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	scanf("%d %d", &H, &W);
	int height, r;
	for (int i = 0; i < W; i++) {
		scanf("%d", &height);
		r = H - 1;
		for (int j = 0; j < height; j++) {
			board[r--][i] = 1;
		}
	}
	printf("%d\n", getRain());
	return 0;
}