문제 URL : https://www.acmicpc.net/problem/20058
문제 접근법 : 문제 자체는 어렵지 않습니다. 단 국어능력이 필요할뿐
회전하는 것은 쉽게 이해할수 있을겁니다. 근데 얼음이 어떡에 줄어드는지 이해를 못해서 몇시간 동안 고민했네요
문제 조건에 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.
얼음이라니 무슨말인가 싶었는데 즉 board안에 1이상 있다면 얼음이 있고
인접한것이 좌우상하 3개이상 있어야 녹지않는다는 뜻입니다.
즉 3개미만이면 해당자리는 녹는것을 표현해줘야합니다.
그리고 마지막으로 L에 해당하는 모든것을 회전하면서 녹일것을 녹인후
모든 얼음의양의 합을 출력하는것과
얼음이 좌우상하로 인접해있는것들중 영역이 가장큰것을 계산해서 출력하면되는데
dfs나 bfs 아무거나 사용하시면됩니다.
소스코드 :
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<vector<int>> board;
vector<int> lv;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int check[64][64];
void input() {
cin >> n >> q;
board = vector<vector<int>>((1 << n), vector<int>(1 << n));
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < (1 << n); j++) {
cin >> board[i][j];
}
}
lv.resize(q);
for (int i = 0; i < q; i++)
cin >> lv[i];
}
void rotate2(int y,int x,int size,vector<vector<int>> &temp) {
for (int i = y,j2=x+size-1; i < y + size; i++,j2--) {
for (int j = x,i2=y; j < x + size; j++,i2++) {
board[i2][j2] = temp[i][j];
}
}
}
void rotate(int l) {
vector<vector<int>> temp = board;
for (int i = 0; i < (1 << n); i+=(1<<l)) {
for (int j = 0; j < (1 << n); j += (1 << l)) {
rotate2(i, j, 1 << l, temp);
}
}
}
bool isrange(int y, int x) {
return 0 <= y && y < (1 << n) && 0 <= x && x < (1 << n);
}
int dfs(int y, int x) {
if (!isrange(y, x))return 0;
if (check[y][x]||board[y][x]==0)return 0;
check[y][x] = 1;
int res = 1;
for (int i = 0; i < 4; i++) {
res += dfs(y + dy[i], x + dx[i]);
}
return res;
}
void solve() {
for (int l : lv) {
rotate(l);
vector<vector<int>> temp = board;
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < (1 << n); j++) {
int cnt = 0;
for (int k = 0; k < 4&&board[i][j]; k++) {
int ny = i + dy[k];
int nx = j + dx[k];
if (!isrange(ny, nx))continue;
if (temp[ny][nx])cnt++;
}
if (cnt < 3&&board[i][j])
board[i][j]--;
}
}
}
int res = 0;
int res2 = 0;
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < (1 << n); j++) {
res += board[i][j];
res2 = max(res2, dfs(i, j));
}
}
cout << res << "\n";
cout << res2 << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
백준 1024 수열의합 (0) | 2021.08.15 |
---|---|
백준 1043 거짓말 (0) | 2021.08.15 |
백준 19238 스타트 택시 (0) | 2021.08.11 |
백준 1948 임계경로 (0) | 2021.08.04 |
백준 3111 검열 (0) | 2021.08.04 |