[PS] 백준 21610번: 마법사 상어와 비바라기

마법사 상어와 비바라기

 

#include <bits/stdc++.h>

#define pii pair<int, int>
#define endl "\n"
using namespace std;

int dr[8] = { +0, -1, -1, -1, +0, +1, +1, +1 };
int dc[8] = { -1, -1, +0, +1, +1, +1, +0, -1 };

int dr2[4] = { -1, -1, +1, +1 };
int dc2[4] = { -1, +1, -1, +1 };

int N, M;
int MAP[50][50];
vector<pii> orders;
vector<pii> clouds;

#define iib(r, c) (0 <= r && r < N && 0 <= c && c < N)

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> MAP[i][j];
	for (int i = 0; i < M; i++) {
		int _a, _b; cin >> _a >> _b;
		orders.emplace_back(_a, _b);
	}

	clouds.emplace_back(N - 1, 0), clouds.emplace_back(N - 1, 1);
	clouds.emplace_back(N - 2, 0), clouds.emplace_back(N - 2, 1);

	for (int cnt = 0; cnt < M; cnt++) {
		int d, s; tie(d, s) = orders[cnt]; d -= 1;

		// 이동
		for (auto& p : clouds) {
			int r, c; tie(r, c) = p;
			p = make_pair((r + dr[d] * s + N * 1000) % N, (c + dc[d] * s + N * 1000) % N);
		}

		vector<pii> mvpos;
		bool bMAP[50][50] = { false, };
		for (auto& p : clouds) {
			int r, c; tie(r, c) = p;
			MAP[r][c] += 1;
			mvpos.emplace_back(r, c);
			bMAP[r][c] = true;
		}
		clouds.clear();


		// 배열 증가
		int cMAP[50][50];
		copy(&MAP[0][0], &MAP[0][0] + 50 * 50, &cMAP[0][0]);
		for (auto& p : mvpos) {
			int r, c, num_non0 = 0; tie(r, c) = p;
			for (int i = 0; i < 4; i++) {
				int nr = r + dr2[i], nc = c + dc2[i];
				if (iib(nr, nc) && MAP[nr][nc] != 0) num_non0 += 1;
			}
			cMAP[r][c] += num_non0;
		}

		copy(&cMAP[0][0], &cMAP[0][0] + 50 * 50, &MAP[0][0]);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (MAP[i][j] >= 2 && !bMAP[i][j]) {
					clouds.emplace_back(i, j);
					MAP[i][j] -= 2;
				}
			}
		}
	}

	int sum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			sum += MAP[i][j];
		}
	}
	cout << sum << endl;
}