글 읽기 - n = 1일때만 성립하는 이유가 뭘까요?

math_rabbit_1028 4년 전 0

부문문제 1, 2인 n = 1인 경우만 정답으로 나옵니다. 어디가 잘못된건가요?

코드 설명

가장자리 구멍부터 시작해 DFS를 시작한다.
전 칸의 물의 높이가 통과하는 구멍의 높이보다 더 작으면 물의 높이를 통과하는 구멍의 높이로 지정한다.
전 칸의 물의 높이가 통과하는 구멍의 높이보다 더 크면 물의 높이를 전 칸의 물의 높이로 지정한다.
모든 구멍에 대해 1 ~ 3 과정을 반복한다.
전체 물 높이를 모두 더해 답을 출력한다.

/*
===========================================================================
 기준 좌표 : (0, 0)
 n : 세로      m : 가로       h : 높이
 hole1[n + 1][m] : 가로 구멍  hole2[n][m + 1] : 세로 구멍
 water_high[n][m] : 수위
 ch1[n + 1][m] : 가로 구멍    ch2[n][m + 1] : 세로 구멍
 Tank1 (x 좌표, y 좌표) : 가장자리 구멍(DFS)
===========================================================================
*/

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, h, hole1[1010][1010], hole2[1010][1010], water_high[1010][1010];
int ch1[1010][1010], ch2[1010][1010], res = 0;

void Tank(int x, int y) {
	if (ch1[x][y] == 0 && hole1[x][y] != -1 && !(x == 0 || x == n)) {
		ch1[x][y] = 1;
		if (water_high[x - 1][y] > max(hole1[x][y], water_high[x][y]))
			water_high[x - 1][y] = max(hole1[x][y], water_high[x][y]);
		Tank(x - 1, y);
	}
	if (ch1[x + 1][y] == 0 && hole1[x + 1][y] != -1 && !(x + 1 == 0 || x + 1 == n)) {
		ch1[x + 1][y] = 1;
		if (water_high[x + 1][y] > max(hole1[x + 1][y], water_high[x][y]))
			water_high[x + 1][y] = max(hole1[x + 1][y], water_high[x][y]);
		Tank(x + 1, y);
	}
	if (ch2[x][y] == 0 && hole2[x][y] != -1 && !(y == 0 || y == m)) {
		ch2[x][y] = 1;
		if (water_high[x][y - 1] > max(hole2[x][y], water_high[x][y]))
			water_high[x][y - 1] = max(hole2[x][y], water_high[x][y]);
		Tank(x, y - 1);
	}
	if (ch2[x][y + 1] == 0 && hole2[x][y + 1] != -1 && !(y + 1 == 0 || y + 1 == m)) {
		ch2[x][y + 1] = 1;
		if (water_high[x][y + 1] > max(hole2[x][y + 1], water_high[x][y]))
			water_high[x][y + 1] = max(hole2[x][y + 1], water_high[x][y]);
		Tank(x, y + 1);
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	//freopen("output.txt", "wt", stdout);
	cin >> n >> m >> h;
	for (int i = 0; i <= n; i++) for (int j = 0; j < m; j++) cin >> hole1[i][j];
	for (int i = 0; i < n; i++) for (int j = 0; j <= m; j++) cin >> hole2[i][j];
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) water_high[i][j] = h;
	for (int j = 0; j < m; j++) {
		if (hole1[0][j] != -1) {
			if (water_high[0][j] > hole1[0][j]) water_high[0][j] = hole1[0][j];
			for (int i = 0; i <= n; i++) for (int k = 0; k < m; k++) ch1[i][k] = 0;
			for (int i = 0; i < n; i++) for (int k = 0; k <= m; k++) ch2[i][k] = 0;
			ch1[0][j] = 1;
			Tank(0, j);
		}
		if (hole1[n][j] != -1) {
			if (water_high[n - 1][j] > hole1[n][j]) water_high[n - 1][j] = hole1[n][j];
			for (int i = 0; i <= n; i++) for (int k = 0; k < m; k++) ch1[i][k] = 0;
			for (int i = 0; i < n; i++) for (int k = 0; k <= m; k++) ch2[i][k] = 0;
			ch1[n][j] = 1;
			Tank(n - 1, j);
		}
	}
	for (int i = 0; i < n; i++) {
		if (hole2[i][0] != -1) {
			if (water_high[i][0] > hole2[i][0]) water_high[i][0] = hole2[i][0];
			for (int j = 0; j <= n; j++) for (int k = 0; k < m; k++) ch1[j][k] = 0;
			for (int j = 0; j < n; j++) for (int k = 0; k <= m; k++) ch2[j][k] = 0;
			ch2[i][0] = 1;
			Tank(i, 0);
		}
		if (hole2[i][m] != -1) {
			if (water_high[i][m - 1] > hole2[i][m]) water_high[i][m - 1] = hole2[i][m];
			for (int j = 0; j <= n; j++) for (int k = 0; k < m; k++) ch1[j][k] = 0;
			for (int j = 0; j < n; j++) for (int k = 0; k <= m; k++) ch2[j][k] = 0;
			ch2[i][m] = 1;
			Tank(i, m - 1);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			res = res + water_high[i][j];
			//cout << water_high[i][j] << " ";
		}
		//cout << '\n';
	}
	cout << res;
	return 0;
}

rootsquare 1년 전 0

구멍의 높이가 낮은 순서대로 BFS를 해야 정확합니다. 그리고 물은 모두 밖으로 빼야 하므로, 내부에 아무리 구멍이 많아도 밖으로 나가는 구멍이 없으면 물은 빠지지 않습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

n = 1일때만 성립하는 이유가 뭘까요?

math_rabbit_1028 4년 전 0

rootsquare 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말