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

sol : 63' 40''

Learnings

• 그리드 밖을 벗어나는 경우의 로직 처리에 대해서 더 깔끔하게 할 수도 있다.

//  1-based
int ni = (i - 1 + ds[curDir][0] * curDist + n) % n + 1;
int nj = (j - 1 + ds[curDir][1] * curDist + n) % n + 1;

// 0-based
int ni = (i + ds[curDir][0] * curDist + n) % n;
int nj = (j + ds[curDir][1] * curDist + n) % n;

#include <iostream>
#include <utility>

using namespace std;

#define MAX_N 51
#define MAX_M 101

const int ds[9][2] = {
	{0, 0},
	{0, -1},
	{-1, -1},
	{-1, 0},
	{-1, 1},
	{0, 1},
	{1, 1},
	{1, 0},
	{1, -1}
};
int rainGrid[MAX_N][MAX_N];
int tempRainGrid[MAX_N][MAX_N];
bool cloudGrid[MAX_N][MAX_N];
bool tempCloudGrid[MAX_N][MAX_N];

struct Order {
	int dir;
	int dist;

	Order() {}
	Order (int _dir, int _dist) :
		dir(_dir), dist(_dist) { }
};

int n, m;
// d방향, s칸
Order orders[MAX_M];

void DebugRG() {
	cout << endl << "DEBUG" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << rainGrid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void DebugCG() {
	cout << endl << "DEBUG" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << cloudGrid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void Bibaragi() {
	cloudGrid[n][1] = true;
	cloudGrid[n][2] = true;
	cloudGrid[n - 1][1] = true;
	cloudGrid[n - 1][2] = true;
}

void InitCloudGrid() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cloudGrid[i][j] = false;
		}
	}
}

void InitTempCloudGrid() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			tempCloudGrid[i][j] = false;
		}
	}
}

bool InGrid_i(int i) {
	return 1 <= i && i <= n;
}

bool InGrid_j(int j) {
	return 1 <= j && j <= n;
}

void DupGrid(auto from[MAX_N][MAX_N], auto to[MAX_N][MAX_N]) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			to[i][j] = from[i][j];
		}
	}
}

void Init() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> rainGrid[i][j];
		}
	}

	for (int i = 1; i <= m; i++) {
		cin >> orders[i].dir >> orders[i].dist;
	}

	Bibaragi();
}

int RowLink(int i) {
	int linked_i = 0;
	if (i <= 0) linked_i = n + i;
	else if (i > n) linked_i = i - n;
	return linked_i;
}

int ColLink(int j) {
	int linked_j = 0;
	if (j <= 0) linked_j = n + j;
	else if (j > n) linked_j = j - n;
	return linked_j;
}

void CloudMove(int turn) {
	InitTempCloudGrid();
	int curDir = orders[turn].dir, curDist = orders[turn].dist;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (!cloudGrid[i][j]) continue;

			curDist = curDist % n;
			int ni = i + ds[curDir][0] * curDist, nj = j + ds[curDir][1] * curDist;
			if (!InGrid_i(ni)) ni = RowLink(ni);
			if (!InGrid_j(nj)) nj = ColLink(nj);

			tempCloudGrid[ni][nj] = true;
		}
	}

	DupGrid(tempCloudGrid, cloudGrid);
}

void Rain() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (cloudGrid[i][j]) {
				rainGrid[i][j]++;
			}
		}
	}
}

void RemoveCloud() {
	DupGrid(cloudGrid, tempCloudGrid);
	InitCloudGrid();
}

void WaterBug() {
	DupGrid(rainGrid, tempRainGrid);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (!tempCloudGrid[i][j]) continue;

			int cnt = 0;
			for (int d = 2; d <= 8; d += 2) {
				int ni = i + ds[d][0], nj = j + ds[d][1];

				if (!InGrid_i(ni) || !InGrid_j(nj)) continue;
				if (rainGrid[ni][nj] > 0) cnt++;
			}

			tempRainGrid[i][j] += cnt;
		}
	}

	DupGrid(tempRainGrid, rainGrid);
}

void GenCloud() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (tempCloudGrid[i][j]) continue;
			if (rainGrid[i][j] >= 2) {
				cloudGrid[i][j] = true;
				rainGrid[i][j] -= 2;
			}
		}
	}
}

void PrintAnswer() {
	int total = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (rainGrid[i][j] > 0) {
				total += rainGrid[i][j];
			}
		}
	}

	cout << total;
}

int main() {
	Init();

	for (int turn = 1; turn <= m; turn++) {
		CloudMove(turn);

		Rain();

		RemoveCloud();

		WaterBug();

		GenCloud();
	}

	PrintAnswer();

	return 0;
}