마법사 상어와 파이어스톰 C++

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

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

#include <iostream>
#include <math.h>
#include <cstring>
#include <algorithm>

using namespace std;
const int MAX = 70;
int n, q,l;
int map[MAX][MAX];
int tmp[MAX][MAX];
int sz;
struct MOVE{ int x,y; };
MOVE mv[4] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
int maxsize = 0;
int counts = 0;

void copymap() {
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) {
			tmp[i][j] = map[i][j];
		}
	}
}

void Rotate(int mi,int mj) {
	int li = pow(2, l);

	int si = mi + li - 1;
	int sj = mj;
	for (int i = mi; i < mi + li; i++) {
		si = mi + li - 1;
		for (int j = mj; j < mj + li; j++) {
			map[i][j] = tmp[si][sj];
			si--;
		}
		sj++;
	}
}

void Divide() {
	copymap();

	for (int i = 0; i < sz; i+=pow(2,l)) {
		for (int j = 0; j < sz; j+=pow(2,l)) {
			Rotate(i, j);
		}
	}
}

void MeltingIce() {
	copymap();

	for (int i = 0; i <sz; i++) {
		for (int j = 0; j < sz; j++) {
			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 < sz && movej >= 0 && movej < sz) {
					if (tmp[movei][movej] > 0) {
						count++;
					}
				}
			}
			if (count < 3 && map[i][j] >0) {
				map[i][j] -= 1;
			}
		}
	}
}

void dfs(int mi, int mj) {
	for (int k = 0; k < 4; k++) {
		int movei = mi + mv[k].x;
		int movej = mj + mv[k].y;

		if (movei >= 0 && movei < sz && movej >= 0 && movej < sz) {
			if (tmp[movei][movej] == 0 && map[movei][movej] > 0) {
				tmp[movei][movej] = 1;
				counts += 1;
				dfs(movei, movej);
			}
		}
	}
}

int main(void) {
	cin >> n >> q;

	sz = pow(2, n);
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) {
			cin >> map[i][j];
		}
	}

	for (int testcase = 0; testcase < q; testcase++) {
		cin >> l;

		Divide();
		MeltingIce();
	}

	int answer = 0;

	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) {
			answer += map[i][j];
		}
	}
	
	memset(tmp, 0, sizeof(tmp));
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) {
			if (map[i][j] > 0 && tmp[i][j] == 0) {
				tmp[i][j] = 1;
				counts = 1;
				dfs(i, j);
				maxsize = max(counts, maxsize);
			}
		}
	}
	cout << answer << endl;
	cout << maxsize << endl;
}