문제 URL : https://www.acmicpc.net/problem/1113
1113번: 수영장 만들기
지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이
www.acmicpc.net
문제 접근법 :
문제가 좀 어려웠습니다. 안쪽에서 물을 어떻게 채울지 생각하니까 답이 안나와 안산학생이라는 블로그를 참고하여
바깥에서부터 물을 채워넣는 다는 생각을 하신걸 보니 답이 바로 떠오르더군요
바깥에서부터 1씩 물을채운후 안쪽에서 채워진물보다 작은 높이라면 그곳은 물을 채워넣을수 있다라는 뜻이 되던구요
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
//By
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
int n, m;
vvi board;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int Max = 0;
void input() {
cin >> n >> m;
board = vvi(n+2, vi(m+2));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c;
cin >> c;
board[i][j] = c - '0';
Max = max(Max, board[i][j]);
}
}
}
bool isrange(int y, int x) {
return 0 <= y && y <= n + 1 && 0 <= x && x <= m + 1;
}
void bfs(int h) {
queue < pair<int, int>> q;
q.push({ 0,0 });
vvi check(n + 2, vi(m + 2));
check[0][0] = 1;
board[0][0] = h;
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && !check[ny][nx] && board[ny][nx] < h) {
q.push({ ny,nx });
check[ny][nx] = 1;
board[ny][nx] = h;
}
}
}
}
void solve() {
int ans = 0;
for (int h = 1; h <= Max; h++) {
bfs(h);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (h > board[i][j]) {
ans++;
board[i][j]++;
}
}
}
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 1715 카드 정렬하기 (0) | 2021.10.30 |
|---|---|
| 백준 8972 미친 아두이노 (0) | 2021.10.24 |
| 백준 2666 벽장문의 이동 (0) | 2021.10.05 |
| 백준 10835 카드게임 (0) | 2021.10.05 |
| 백준 16401 과자 나눠주기 (0) | 2021.10.05 |
