본문 바로가기
백준

백준 20058 마법사 상어와 파이어스톰

by 콩순이냉장고 2021. 8. 13.

문제 URL : https://www.acmicpc.net/problem/20058

 

20058번: 마법사 상어와 파이어스톰

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c

www.acmicpc.net

문제 접근법 : 문제 자체는 어렵지 않습니다. 단 국어능력이 필요할뿐 

회전하는 것은 쉽게 이해할수 있을겁니다. 근데 얼음이 어떡에 줄어드는지 이해를 못해서 몇시간 동안 고민했네요

 

문제 조건에 얼음이 있는 칸 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