[백준 15730] 수영장 사장님

아 memset ㅡㅡ cstring 넣으라고 ㅡㅡ

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

15730번: 수영장 사장님

#include <cstdio>
#include <queue>
#include <cstring>
int R, C;
int H[100 + 2][100 + 2];
int max_h;

struct _st
{
	int x, y;
};

std::queue<_st> Q;
int visited[100 + 2][100 + 2];

void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			scanf("%d", &H[i][j]);
			if (max_h < H[i][j]) max_h = H[i][j];
		}
	}
}

void make_bound()
{
	for (int i = 0; i <= R + 1; i++) {
		H[i][0] = 0;
		H[i][C + 1] = 0;
	}
	for (int j = 0; j <= C + 1; j++) {
		H[0][j] = 0;
		H[R + 1][j] = 0;
	}
}


void BFS(int rain)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	Q = {};
	memset(visited, 0, sizeof(visited));

	H[0][0] = rain;
	Q.push({ 0, 0 });
	visited[0][0] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R + 1 || ny < 0 || ny > C + 1) continue;
			if (visited[nx][ny]) continue;
			if (H[nx][ny] < rain) {
				H[nx][ny] = rain;
				Q.push({ nx, ny });
				visited[nx][ny] = 1;
			}
		} 
	} 
}




int make_pool()
{
	int total = 0;
	for (int r = 1; r <= max_h; r++) {
		BFS(r);

		// chk can fill area
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				if (H[i][j] < r) {
					total++;
					H[i][j]++;
				}
			}
		}
	}
	return total;
} 


int main()
{
	input();
	make_bound();
	int ans = make_pool();
	printf("%d\n", ans);
	return 0;
}

 

수영장 사장님을 풀었다면 ? => "[백준 1113] 수영장 만들기" 도 풀어보자 

걍 똑같은 문제 

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

1113번: 수영장 만들기