본문 바로가기
백준 알고리즘/DFS

마법사 상어와 파이어스톰

by paysmile 2021. 4. 1.

https://www.acmicpc.net/problem/20058

 

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

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

www.acmicpc.net

 

#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