마법사 상어와 파이어스톰 (feat. 백준, 20058번)

마법사 상어와 파이어스톰
https://www.acmicpc.net/problem/20058

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

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/20058
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int N, Q, arr[64][64], arr_tmp[64][64], visit[64][64], dx[4], dy[4];
inline void turn_clockwise(const int& x1, const int& y1, const int& x2, const int& y2) {
	// turn clockwise
	for (int ix = x1, iy; ix < x2; ++ix)
		for (iy = y1; iy < y2; ++iy)
			arr_tmp[x1 + (iy - y1)][(y2 - 1) - (ix - x1)] = arr[ix][iy];
	// tmp -> orig
	for (int ix = x1, iy; ix < x2; ++ix)
		for (iy = y1; iy < y2; ++iy)
			arr[ix][iy] = arr_tmp[ix][iy];
}
inline void solve(const int& l) {
	// 격자 나누고 시계방향
	if (l > 1)
		for (int ix = 0, iy; ix < N; ix += l)
			for (iy = 0; iy < N; iy += l)
				turn_clockwise(ix, iy, ix + l, iy + l);
	// 인접한 곳중 얼음이 있는 곳이 2곳 이하면 -1을 취함
	for (int ix = 0, iy; ix < N; ++ix)
		for (iy = 0; iy < N; ++iy)
			arr_tmp[ix][iy] = 0;
	for (int ix = 0, iy, d, nx, ny, count; ix < N; ++ix)
		for (iy = 0; iy < N; ++iy) {
			if (arr[ix][iy] > 0) {
				for (d = 0, count = 0; d < 4; ++d) {
					nx = ix + dx[d], ny = iy + dy[d];
					if (0 <= nx && nx < N && 0 <= ny && ny < N && arr[nx][ny] > 0)
						++count;
				}
				if (count < 3)		--arr_tmp[ix][iy];
			}
		}
	for (int ix = 0, iy; ix < N; ++ix)
		for (iy = 0; iy < N; ++iy)
			arr[ix][iy] += arr_tmp[ix][iy];
}
inline int calc_mass(int x, int y) {
	auto count = 1;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visit[x][y] = 1;
	while (!q.empty()) {
		auto pos = q.front(); q.pop();
		x = pos.first, y = pos.second;
		for (int idx = 0, nx, ny; idx < 4; ++idx) {
			nx = x + dx[idx], ny = y + dy[idx];
			if (0 <= nx && nx < N && 0 <= ny && ny < N && !visit[nx][ny] && arr[nx][ny]>0)
				++count, visit[nx][ny] = 1, q.push(make_pair(nx, ny));
		}
	}
	return count;
}
inline void result() {
	auto total_ice_value = 0, max_mass_count = 0;
	for (int ix = 0, iy; ix < N; ++ix)
		for (iy = 0; iy < N; ++iy) {
			total_ice_value += arr[ix][iy];
			if (!visit[ix][iy] && arr[ix][iy] > 0)
				max_mass_count = max(max_mass_count, calc_mass(ix, iy));
		}
	cout << total_ice_value << endl << max_mass_count << endl;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	for (int ix = 0, iy; ix < 64; ++ix)
		for (iy = 0; iy < 64; ++iy)
			arr[ix][iy] = visit[ix][iy] = 0;
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N >> Q;
	N = static_cast<int>(pow(2, N));
	for (int ix = 0, iy; ix < N; ++ix)
		for (iy = 0; iy < N; ++iy)
			cin >> arr[ix][iy];
	for (int q = 0, l; q < Q; ++q) {
		cin >> l;
		solve(static_cast<int>(pow(2, l)));
	}
	result();
	return 0;
}
// *&)*@*

1. 얼음이 감소하는 조건은 현재 위치의 상,하,좌,우 기준 얼음이 있는 칸(0보다 큰)이 3개 미만일 경우입니다.
2. 그리고 지문에는 적혀있지 않지만 1번의 과정이 '동시에' 일어납니다. 즉, 하나씩 검사하면서 감소하는 결과는 따로 담고, 모두 다 검사한 이후에 적용해야 합니다.
3. 시계 방향으로 2차원 배열을 돌리는 것은 turn_clockwise 함수를 참고하시면 되겠습니다. 2차원 배열은 (0,0) ~ (2^N -1, 2^N - 1) 입니다.