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

2224KB, 52ms

 

• BFS, 행렬 회전 문제
  • [q-j-i][pow(2,L)-(p-i)+j]
• 주의사항
  • 0을 출력하라고 한게 그냥 0이 아니라 maxblock에 0을 출력하라고 한거임.. 에바

#include <iostream>
#include <cmath>
#include <queue>
#include <iomanip>

#define MAX 64
using namespace std;

int N, Q, L, map[MAX][MAX] = {};
int pow2N;

int dy[4] = { -1,1,0,0 }, dx[4] = { 0,0,-1,1 };

void input() {
	cin >> N >> Q;
	pow2N = pow(2, N);
	for (int i = 0; i < pow2N; i++)
		for (int j = 0; j < pow2N; j++)
			cin >> map[i][j];
}

void turn() {
	int copy_map[MAX][MAX] = {};
	for (int i = 0; i < pow2N; i++)
		for (int j = 0; j < pow2N; j++)
			copy_map[i][j] = map[i][j];

	int jump = pow(2, L);
	for (int i = 0; i < pow2N; i += jump) 
		for (int j = 0; j < pow2N; j += jump) 
			for (int p = i; p < i + jump; p++) 
				for (int q = j; q < j + jump; q++) 
					map[q - j + i][jump -1 - (p - i) + j] = copy_map[p][q];
}

void melt() {
	int copy_map[MAX][MAX] = {};
	for (int i = 0; i < pow2N; i++)
		for (int j = 0; j < pow2N; j++)
			copy_map[i][j] = map[i][j];

	for (int i = 0; i < pow2N; i++) {
		for (int j = 0; j < pow2N; j++) {
			if (copy_map[i][j] == 0) continue;
			int cnt = 0;
			for (int k = 0; k < 4; k++) {
				int y = i + dy[k], x = j + dx[k];
				if (y >= pow2N || x >= pow2N || y < 0 || x < 0) continue;
				if (copy_map[y][x] > 0) cnt++;
			}
			if (cnt < 3) map[i][j]--;
		}
	}
}

void solve() {
	while (Q--) {
		cin >> L;
		turn();
		melt();
	}
}

void result() {
	bool visited[MAX][MAX] = {};
	int res = 0;
	int maxblock = 0;

	queue<pair<int, int>> q;

	for (int i = 0; i < pow2N; i++) {
		for (int j = 0; j < pow2N; j++) {
			if (visited[i][j] || map[i][j] == 0) continue;
			visited[i][j] = true;
			q.push({i, j});

			int cnt = 0;
			while (!q.empty()) {
				int y = q.front().first, x = q.front().second;
				cnt++;
				q.pop();
				res += map[y][x];

				for (int i = 0; i < 4; i++) {
					int new_y = y + dy[i], new_x = x + dx[i];
					if (new_y >= pow2N || new_y < 0 || new_x >= pow2N || new_x < 0
						|| map[new_y][new_x] == 0 || visited[new_y][new_x]) continue;

					visited[new_y][new_x] = true;
					q.push({ new_y, new_x });
				}
			}
			maxblock = maxblock < cnt ? cnt : maxblock;
		}
	}
	cout << res << '\n' << maxblock;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	solve();
	result();
}