https://www.acmicpc.net/problem/20058
20058번: 마법사 상어와 파이어스톰
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c
www.acmicpc.net
재귀 + 배열 돌리기와 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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n, kugi, q;
int map[100][100];
bool visited[100][100];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int ans1 = 0;
int ans2 = 0;
void melt()
{
vector<pair<int, int>> v;
for (int i = 0; i < kugi; i++)
{
for (int j = 0; j < kugi; j++)
{
int cnt = 0;
if (map[i][j] == 0)
continue;
int flag = 0;
for (int k = 0; k < 4; k++)
{
int nx = i + dx[k];
int ny = j + dy[k];
if (nx >= 0 && nx < kugi && ny >= 0 && ny < kugi)
{
if (map[nx][ny] != 0)
cnt++;
}
}
// 얼음 있는 칸이 3개보다 적으면
// 녹여야하므로 좌표 저장
if (cnt < 3)
v.push_back(make_pair(i, j));
}
}
for (int i = 0; i < v.size(); i++)
{
int x = v[i].first;
int y = v[i].second;
map[x][y]--;
ans1--;
}
}
int bfs(int a, int b)
{
queue<pair<int, int>> q;
q.push(make_pair(a, b));
visited[a][b] = true;
int tmp = 1;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < kugi && ny >= 0 && ny < kugi && !visited[nx][ny])
{
if (map[nx][ny] != 0)
{
visited[nx][ny] = true;
q.push(make_pair(nx, ny));
tmp++;
}
}
}
}
return tmp;
}
void go(int sx, int sy, int step, int goal)
{
if (step == goal) {
// rotate
int tmp[80][80] = { 0, };
int genkai = 1 << step;
for (int i = sx; i < sx + genkai; i++)
{
for (int j = sy; j < sy + genkai; j++)
tmp[i][j] = map[i][j];
}
// 시계 방향 회전
for (int j = sy + genkai - 1, tmp_x = sx; j >= sy; j--, tmp_x++)
{
for (int i = sx, tmp_y = sy; i < sx + genkai; i++, tmp_y++)
{
map[i][j] = tmp[tmp_x][tmp_y];
}
}
return;
}
int diff = 1 << (step - 1);
go(sx, sy, step - 1, goal);
go(sx, sy + diff, step - 1, goal);
go(sx + diff, sy, step - 1, goal);
go(sx + diff, sy + diff, step - 1, goal);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
kugi = 1 << n;
for (int i = 0; i < kugi; i++)
{
for (int j = 0; j < kugi; j++)
{
cin >> map[i][j];
// 처음에 얼음 개수를 저장
// melt에서 녹이면서 ans1을 줄인다
ans1 += map[i][j];
}
}
while (q--)
{
int l;
cin >> l;
go(0, 0, n, l);
melt();
}
for (int i = 0; i < kugi; i++)
{
for (int j = 0; j < kugi; j++)
{
if (map[i][j] == 0)
continue;
if (visited[i][j] == true) continue;
int result = bfs(i, j);
ans2 = max(ans2, result);
}
}
cout << ans1 << '\n' << ans2;
return 0;
}
|
cs |
