https://www.acmicpc.net/problem/20058
#include <iostream>
#include <cstring>
#include <cmath>
const int MAX = 65;
int q,n,l;
int A[MAX][MAX];
int num;
int temp[MAX][MAX];
struct MOVE { int x,y; };
MOVE mv[4] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int visited[MAX][MAX];
int sum = 0;
using namespace std;
void copymap() {
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= num; j++) {
temp[i][j] = A[i][j];
}
}
}
void RotateMap() {
int line = pow(2, l);
int count_i = num / line;
int loc_i = 1;
int loc_j = 1;
while (loc_i <= count_i) {
int index_i = loc_i * line - (line-1);
loc_j = 1;
while (loc_j <= count_i) {
int index_j = loc_j * line - (line - 1);
for (int i = 0; i < line; i++) {
int movei = i + index_i;
for (int j = 0; j < line; j++) {
int movej = j + index_j;
A[movei][movej] = temp[loc_i*line-j][index_j + i];
}
}
loc_j += 1;
}
loc_i += 1;
}
}
void MeltingIce() {
copymap();
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= num; j++) {
if (A[i][j] > 0) {
int count = 0;
for (int k = 0; k < 4; k++) {
int movei = i + mv[k].x;
int movej = j + mv[k].y;
if (!(movei <= 0 || movei > num || movej <= 0 || movej > num)) {
if (temp[movei][movej] > 0)
count += 1;
}
}
if (count < 3)
A[i][j] -= 1;
}
}
}
}
int sumIce() {
int answer = 0;
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= num; j++) {
answer += A[i][j];
}
}
return answer;
}
void dfs(int i, int j) {
for (int k = 0; k < 4; k++) {
int movei = i + mv[k].x;
int movej = j + mv[k].y;
if (movei >= 1 && movei <= num && movej >= 1 && movej <= num) {
if (visited[movei][movej] == -1) {
if (A[movei][movej] > 0) {
visited[movei][movej] = 1;
sum += 1;
dfs(movei, movej);
}
}
}
}
}
int BiggestIce() {
int answer = 0;
memset(visited, -1, sizeof(visited));
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= num; j++) {
if (A[i][j] > 0 && visited[i][j] == -1) {
sum = 0;
dfs(i, j);
if (sum > answer)
answer = sum;
}
}
}
return answer;
}
int main(void) {
cin >> n >> q;
num = pow(2, n);
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= num; j++) {
cin >> A[i][j];
}
}
for (int i = 0; i < q; i++) {
cin >> l;
copymap();
RotateMap();
MeltingIce();
}
cout << sumIce() << endl;
cout << BiggestIce() << endl;
}
'백준 알고리즘 > DFS' 카테고리의 다른 글
상어 중학교 C++ (0) | 2021.09.18 |
---|---|
원판 돌리기 (0) | 2021.04.20 |
청소년 상어 C++ (0) | 2021.03.08 |
마법사 상어와 파이어스톰 C++ (0) | 2021.02.28 |
마법사 상어와 파이어스톰 C++ (0) | 2021.02.28 |