法師サメとクローン(23290)

1.問題リンク
質問リンク
2.解答
1.地図デザイン

vector<int> fishs[4][4], prepare[4][4];

2 Dバックグラウンドアレイとして設計されています.
後土に魚の方向があります.fishsは魚とサメの移動をシミュレートした地図です.prepareは魚の複製を準備する誤った地図です.
2.サメのすべての移動経路を昇順に並べる

vector<vector<int>> sharkPaths;

for (int i = 0; i < 4; i++)
	for (int j = 0; j < 4; j++)
		for (int k = 0; k < 4; k++)
			sharkPaths.push_back({ i, j, k });

サメの移動経路も最大64本しかありません.
3重砲口を使用して、すべての経路をsharkPathsに格納します.
3.誤った魔法をコピーする準備

void copyBoard(vector<int> from[][4], vector<int> to[][4]) {
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			to[i][j] = from[i][j];
} 

copyBoard(fishs, prepare);

特にありません.fishsの現在の状態をprepareにコピーします.
4.移動魚

void moveFishs() {
	vector<int> tmp[4][4];

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int d : fishs[i][j]) {
				int isMove = 0;

				// 8방향 시도
				for (int dir = 0; dir < 8; dir++) {
					int y = i + fy[d];
					int x = j + fx[d];

					// 나가지 않았고 물고기 냄새가 없고 상어도 없을 때
					if (!isOut(y, x) && smell[y][x] == 0 && (y != shy || x != shx)) {
						tmp[y][x].push_back(d);
						isMove = 1;
						break;
					}

					d = (d + 7) % 8;
				}

				// 못 움직였을 땐 현재 자리에 현재 방향으로 넣기
				if (!isMove) tmp[i][j].push_back(d);
			}
		}
	}

	copyBoard(tmp, fishs);
}

tmp地図を作成し、魚の活動を記録します.tmpマッピングは、fishsマッピングにコピーされる.
5.魚の味を減らす

void decreaseSmell() {
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			smell[i][j] = max(0, smell[i][j] - 1);
}

電球間を回転させ、1を減らします.
6.移動サメ

void moveShark() {
	int maxFishHuntCnt = -1;
	int pathNum = -1;

	for (int i = 0; i < 64; i++) {
		int fishHuntCnt = 0;
		int ny = shy;
		int nx = shx;
		int isWay = 1;

		for (int d : sharkPaths[i]) {
			ny += sy[d];
			nx += sx[d];

			// 맵을 벗어날 때
			if (isOut(ny, nx)) {
				isWay = 0;
				break;
			}

			// 먹지 않았던 물고기일 때
			if (!eated[ny][nx]) {
				fishHuntCnt += fishs[ny][nx].size();
				eated[ny][nx] = 1; // 먹었다 표시
			}
		}

		ny = shy;
		nx = shx;

		// eated 배열 초기화
		for (int d : sharkPaths[i]) {
			ny += sy[d];
			nx += sx[d];

			if (!isOut(ny, nx)) eated[ny][nx] = 0;
		}

		// 갈 수 있는 길이고 물고기를 더 많이 먹었을 때
		if (isWay && fishHuntCnt > maxFishHuntCnt) {
			maxFishHuntCnt = fishHuntCnt;
			pathNum = i;
		}
	}

	// 상어 이동
	for (int d : sharkPaths[pathNum]) {
		shy += sy[d];
		shx += sx[d];

		if (fishs[shy][shx].size() > 0) {
			smell[shy][shx] = 2; // 물고기 냄새를 2로 설정
			fishs[shy][shx].clear();
		}
	}
}

2番サメのすべての移動経路を調べました.
サメを最も魚を狩る場所に移す
このとき魚を打つときは魚の味を2に設定します.
その後、1のにおいを一歩ずつ減らします.
前段階の魚のにおいを取り除くことができます.
7.水輻射バグ魔法をかける

void copyBug() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int d : prepare[i][j]) {
				fishs[i][j].push_back(d);
			}
		}
	}
}

3番からprepare地図にコピーした魚をfishsに移動します.
3.完全なコード

#include <bits/stdc++.h>

using namespace std;

int m, s, shy, shx;
int fy[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int fx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int sy[4] = { -1, 0, 1, 0 };
int sx[4] = { 0, -1, 0, 1 };
int smell[4][4], eated[4][4];
vector<vector<int>> sharkPaths;
vector<int> fishs[4][4], prepare[4][4];

bool isOut(int y, int x) {
	return y < 0 || y >= 4 || x < 0 || x >= 4;
}

void copyBoard(vector<int> from[][4], vector<int> to[][4]) {
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			to[i][j] = from[i][j];
}

void moveFishs() {
	vector<int> tmp[4][4];

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int d : fishs[i][j]) {
				int isMove = 0;

				// 8방향 시도
				for (int dir = 0; dir < 8; dir++) {
					int y = i + fy[d];
					int x = j + fx[d];

					// 나가지 않았고 물고기 냄새가 없고 상어도 없을 때
					if (!isOut(y, x) && smell[y][x] == 0 && (y != shy || x != shx)) {
						tmp[y][x].push_back(d);
						isMove = 1;
						break;
					}

					d = (d + 7) % 8;
				}

				// 못 움직였을 땐 현재 자리에 현재 방향으로 넣기
				if (!isMove) tmp[i][j].push_back(d);
			}
		}
	}

	copyBoard(tmp, fishs);
}

void decreaseSmell() {
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			smell[i][j] = max(0, smell[i][j] - 1);
}

void moveShark() {
	int maxFishHuntCnt = -1;
	int pathNum = -1;

	for (int i = 0; i < 64; i++) {
		int fishHuntCnt = 0;
		int ny = shy;
		int nx = shx;
		int isWay = 1;

		for (int d : sharkPaths[i]) {
			ny += sy[d];
			nx += sx[d];

			// 맵을 벗어날 때
			if (isOut(ny, nx)) {
				isWay = 0;
				break;
			}

			// 먹지 않았던 물고기일 때
			if (!eated[ny][nx]) {
				fishHuntCnt += fishs[ny][nx].size();
				eated[ny][nx] = 1; // 먹었다 표시
			}
		}

		ny = shy;
		nx = shx;

		// eated 배열 초기화
		for (int d : sharkPaths[i]) {
			ny += sy[d];
			nx += sx[d];

			if (!isOut(ny, nx)) eated[ny][nx] = 0;
		}

		// 갈 수 있는 길이고 물고기를 더 많이 먹었을 때
		if (isWay && fishHuntCnt > maxFishHuntCnt) {
			maxFishHuntCnt = fishHuntCnt;
			pathNum = i;
		}
	}

	// 상어 이동
	for (int d : sharkPaths[pathNum]) {
		shy += sy[d];
		shx += sx[d];

		if (fishs[shy][shx].size() > 0) {
			smell[shy][shx] = 2;
			fishs[shy][shx].clear();
		}
	}
}

void copyBug() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int d : prepare[i][j]) {
				fishs[i][j].push_back(d);
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> s;

	for (int i = 0; i < m; i++) {
		int y, x, d;
		cin >> y >> x >> d;
		fishs[y - 1][x - 1].push_back(d - 1);
	}

	cin >> shy >> shx;
	shy--;
	shx--;

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++)
				sharkPaths.push_back({ i, j, k });

	while (s--) {
		copyBoard(fishs, prepare);
		moveFishs();
		decreaseSmell();
		moveShark();
		copyBug();
	}

	int ans = 0;

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			ans += fishs[i][j].size();

	cout << ans;

	return 0;
}