[코드트리] 미로타워 디펜스

https://www.codetree.ai/training-field/frequent-problems/maze-tower-defense/description?page=2&pageSize=20

코드트리

#include <cstdio>
#include <cstring>
#include <queue>
int N, M;
int board[25 + 2][25 + 2];
int tmp[25 + 2][25 + 2];

struct _ct
{
	int d;
	int p;
};
_ct CMD[100 + 2];

struct _st
{
	int x, y;
};
_st Snail[625 + 2];	// 5번을 위한 달팽이 좌표 
int s_debug[25 + 2][25 + 2];	// 달팽이 좌표 디버깅용 


struct _qt
{
	int x, y;
	int num;
};
std::queue<_qt> FQ;	// gt_four용 큐
std::queue<int> MQ;	// monster pair용 큐



// dir for snail
// 좌 하 우 상
int dir_x[4] = { 0, 1, 0, -1 };
int dir_y[4] = { -1, 0, 1, 0 };



void input()
{
	scanf("%d %d", &N, &M);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			scanf("%d", &board[r][c]);
		}
	}
	for (int i = 1; i <= M; i++) {
		scanf("%d %d", &CMD[i].d, &CMD[i].p);
	}
}

void make_route()
{
	int sx = N / 2;
	int sy = N / 2;
	int p = 0;
	int num = 1;

	for (int n = 1; n <= N - 1; n++) {
		for (int i = 1; i <= 3; i++) {
			if (n != N - 1 && i == 3) break;
			for (int step = 1; step <= n; step++) {
				int nx = sx + dir_x[p];
				int ny = sy + dir_y[p];
				Snail[num] = { nx, ny };
				//s_debug[nx][ny] = num;	// this for debug
				num++;
				sx = nx; sy = ny;
			}
			p = (p + 1) % 4;
		}
	}
}

int del_monster(int dir, int power)
{
	// dir	// 공격용 방향벡터
	int dr[4] = { 0, 1, 0, -1 };
	int dc[4] = { 1, 0, -1, 0 };	

	// init
	int cnt = 0;
	int sx = N / 2;
	int sy = N / 2;

	for (int p = 1; p <= power; p++) {
		int nx = sx + (dr[dir] * p);
		int ny = sy + (dc[dir] * p);
		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) break;	// 더 쏘아봤자 영역밖임
		cnt += board[nx][ny];
		board[nx][ny] = 0;
	}
	return cnt;
}


void re_arrange()
{
	// init 
	int sx = N / 2;
	int sy = N / 2;
	int p = 0;
	int num = 1;
	memset(tmp, 0, sizeof(tmp));

	// board 2 tmp
	for (int n = 1; n <= N - 1; n++) {
		for (int i = 1; i <= 3; i++) {
			if (n != N - 1 && i == 3) break;
			for (int step = 1; step <= n; step++) {
				int nx = sx + dir_x[p];
				int ny = sy + dir_y[p];

				if (board[nx][ny] != 0) {
					tmp[Snail[num].x][Snail[num].y] = board[nx][ny];
					num++;
				}
				sx = nx; sy = ny;
			}
			p = (p + 1) % 4;
		}
	}
	memcpy(board, tmp, sizeof(board));
}


int gt_four()
{
	// init
	int sx = N / 2;
	int sy = N / 2;
	int p = 0;
	int cnt = 0;
	FQ = {};
	
	for (int n = 1; n <= N - 1; n++) {
		for (int i = 1; i <= 3; i++) {
			if (n != N - 1 && i == 3) break;
			for (int step = 1; step <= n; step++) {
				int nx = sx + dir_x[p];
				int ny = sy + dir_y[p];

				if (FQ.empty()) FQ.push({ nx, ny, board[nx][ny] });
				else {
					if (FQ.front().num == board[nx][ny]) FQ.push({ nx ,ny, board[nx][ny] });
					else {
						if (FQ.size() < 4) {
							FQ = {};
							FQ.push({ nx, ny, board[nx][ny] });
						}
						else if (FQ.size() >= 4) {
							cnt += (FQ.front().num * FQ.size());
							while (!FQ.empty()) {
								_qt data = FQ.front();
								FQ.pop();
								board[data.x][data.y] = 0;
							}
							FQ.push({ nx ,ny, board[nx][ny] });
						}
					}
				}
				sx = nx, sy = ny;
			}
			p = (p + 1) % 4;
		}
	}
	return cnt;
}


void make_monster_pair()
{
	// init 
	int sx = N / 2;
	int sy = N / 2;
	int p = 0;
	int num = 1;
	memset(tmp, 0, sizeof(tmp));
	MQ = {};
	bool end = false;

	for (int n = 1; n <= N - 1; n++) {
		for (int i = 1; i <= 3; i++) {
			if (n != N - 1 && i == 3) break;
			for (int step = 1; step <= n; step++) {
				int nx = sx + dir_x[p];
				int ny = sy + dir_y[p];

				if (MQ.empty()) MQ.push(board[nx][ny]);
				else {
					if (MQ.front() == board[nx][ny]) MQ.push(board[nx][ny]);
					else {
						int count = MQ.size();
						int size = MQ.front();
						tmp[Snail[num].x][Snail[num].y] = count;
						num++;
						if (num == N * N) {
							end = true;
							break;
						}
						tmp[Snail[num].x][Snail[num].y] = size;
						num++;
						if (num == N * N) {
							end = true;
							break;
						}
						if (board[nx][ny] == 0) {
							end = true;
							break;
						}

						MQ = {};
						MQ.push(board[nx][ny]);
					}
				}
				sx = nx, sy = ny;
			}
			if (end == true) break;
			p = (p + 1) % 4;
		}
		if (end == true) break;
	}
	memcpy(board, tmp, sizeof(tmp));
}




int simulation()
{
	int score = 0;
	for (int i = 1; i <= M; i++) {
		int res = del_monster(CMD[i].d, CMD[i].p);	// d방향 p만큼 
		score += res;
		re_arrange();
		while (1) {
			int end = gt_four();
			re_arrange();
			if (end == 0) break;
			score += end;
		}
		make_monster_pair();
	}
	return score;
}




int main()
{
	input();
	make_route();
	int ans = simulation();
	printf("%d\n", ans);
	return 0;
}