cgy12306
[백준 BoJ] 1113 - 수영장 만들기 본문
겉에 물이 빠져나갈 수 있는 테두리를 하나 만들어주고, 이후 bfs를 돌려 한 칸씩 바깥의 물을 채워나감과 동시에 안쪽에 채워지지 않는 부분을 체크하여 높이를 구함
// https://www.acmicpc.net/problem/1113
// 수영장 만들기
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int N, M;
int map[52][52];
int Max = 0;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int sum = 0;
queue<pair<int, int>> q;
void bfs(int h) {
map[0][0] = h;
q.push({ 0, 0 });
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx > N + 1 || ny > M + 1) continue;
if (map[nx][ny] < h) {
map[nx][ny] = h;
q.push({ nx, ny });
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
char ch;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> ch;
map[i][j] = ch - '0';
Max = max(map[i][j], Max);
}
}
for (int h = 1; h <= Max; h++) {
bfs(h);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (map[i][j] < h) {
sum++;
map[i][j] += 1;
}
}
}
}
cout << sum;
}
- BFS
'Algorithm > C++' 카테고리의 다른 글
[백준 BoJ] 2206 - 벽 부수고 이동하기 (0) | 2022.03.18 |
---|---|
[백준 BoJ] 24678 - 돌무더기 게임 1 (0) | 2022.03.13 |
[백준 BoJ] 12582 - 1로 만들기 2 (0) | 2022.03.08 |
[백준 BoJ] 2133 - 타일채우기 (0) | 2022.03.08 |
[백준 BoJ] 1357 - 최솟값과 최댓값 (0) | 2022.03.04 |
Comments