마법사 상어와 복제 (feat. 백준, 23290번)

마법사 상어와 복제
https://www.acmicpc.net/problem/23290

23290번: 마법사 상어와 복제

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/23290
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
struct Fish {
	int x, y, d;
};
vector<Fish> fishes[4][4];
vector<Fish> copy_fishes;
int blood[4][4];
int routes[10];
Fish shark;
int M, S;
int dx[8], dy[8], sx[4], sy[4];
int max_eat_fishes;

void copy_fish() {
	for (int x = 0, y; x < 4; ++x)
		for (y = 0; y < 4; ++y)
			if (!fishes[x][y].empty())
				for (const auto& fish : fishes[x][y])
					copy_fishes.push_back(fish);
}
void move_fish() {
	vector<Fish> tmp_fishes[4][4];
	for (int x = 0, y, i, nx, ny; x < 4; ++x)
		for (y = 0; y < 4; ++y)
			if (!fishes[x][y].empty())
				for (auto& fish : fishes[x][y]) {
					for (i = 0; i < 8; ++i) {
						nx = x + dx[fish.d], ny = y + dy[fish.d];
						if (0 <= nx && nx < 4 && 0 <= ny && ny < 4 && blood[nx][ny] == 0 && !(shark.x == nx && shark.y == ny)) {
							fish.x = nx, fish.y = ny, tmp_fishes[nx][ny].push_back(fish);
							break;
						}
						if (--fish.d < 0)		fish.d = 7;
					}
					if (i == 8)
						tmp_fishes[x][y].push_back(fish);
				}
	// copy -> origin
	for (int x = 0, y; x < 4; ++x)
		for (y = 0; y < 4; ++y)
			fishes[x][y] = tmp_fishes[x][y];
}
int move_shark() {
	auto eat_count = 0, x = shark.x, y = shark.y;
	bool visit[4][4] = { false };
	for (int idx = 0, nx, ny; idx < 3; ++idx) {
		nx = x + sx[routes[idx]], ny = y + sy[routes[idx]];
		if (0 <= nx && nx < 4 && 0 <= ny && ny < 4) {
			if (!visit[nx][ny])
				eat_count += static_cast<int>(fishes[nx][ny].size()), visit[nx][ny] = true;
			x = nx, y = ny;
		}
		else
			return -1;
	}
	return eat_count;
}
void find_route(int count) {
	if (count == 3) {
		auto eat_fishes = move_shark();
		if (eat_fishes != -1 && eat_fishes > max_eat_fishes)
			max_eat_fishes = eat_fishes, memcpy(&routes[3], routes, sizeof(int) * 3);
		return;
	}
	for (auto idx = 0; idx < 4; ++idx) {
		routes[count] = idx;
		find_route(count + 1);
	}
}
void real_move_shark() {
	for (int idx = 0, nx, ny; idx < 3; ++idx) {
		nx = shark.x + sx[routes[idx + 3]], ny = shark.y + sy[routes[idx + 3]];
		if (0 <= nx && nx < 4 && 0 <= ny && ny < 4) {
			shark.x = nx, shark.y = ny;
			if (!fishes[nx][ny].empty())
				blood[nx][ny] = 2, fishes[nx][ny].clear();
		}
	}
}
void copy_fish_apply() {
	for(auto iter = copy_fishes.begin(); iter != copy_fishes.end(); ++iter)
		fishes[iter->x][iter->y].push_back(*iter);
	copy_fishes.clear();
}
void decrease_blood() {
	for (int x = 0, y; x < 4; ++x)
		for (y = 0; y < 4; ++y)
			if (blood[x][y] > 0)			--blood[x][y];
}
void solve() {
	copy_fish();
	move_fish();
	decrease_blood();
	max_eat_fishes = -1, find_route(0);
	real_move_shark();
	copy_fish_apply();
}
void answer() {
	auto count = 0;
	for (int x = 0, y; x < 4; ++x)
		for (y = 0; y < 4; ++y)
			if (!fishes[x][y].empty())
				count += static_cast<int>(fishes[x][y].size());
	cout << count << endl;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	dx[0] = dx[4] = 0, dx[1] = dx[2] = dx[3] = -1, dx[5] = dx[6] = dx[7] = 1;
	dy[2] = dy[6] = 0, dy[0] = dy[1] = dy[7] = -1, dy[3] = dy[4] = dy[5] = 1;
	sx[0] = -1, sx[1] = sx[3] = 0, sx[2] = 1;
	sy[0] = sy[2] = 0, sy[1] = -1, sy[3] = 1;
	for (int x = 0, y; x < 4; ++x)
		for (y = 0; y < 4; ++y)
			blood[x][y] = 0;
	cin >> M >> S;
	for (int m = 0, x, y, d; m < M; ++m)
		cin >> x >> y >> d, fishes[x - 1][y - 1].push_back(Fish{ x - 1, y - 1, d - 1 });
	cin >> shark.x >> shark.y, shark.x -= 1, shark.y -= 1;
	for (auto s = 0; s < S; ++s)
		solve();
	answer();
	return 0;
}
// *&)*@*

1. 상어가 움직일 수 있는 상,하,좌,우 는 우선순위가 있습니다. 해당 페이지 하단에 '노트'라고 적혀있는 부분입니다. (이거때문에 한시간 이상은 날렸습니다.)
2. 조합이 아닌 순열로 상어는 움직일 수 있습니다. 즉, 상-하-상 으로 갈 수 있습니다. 단, 상-하-상 에서 마지막 상일 경우, 물고기를 이미 첫번째 상에서 먹었기 때문에, 반드시 체크해주어야 합니다.
3. copy_fishes를 queue로 사용하였으나, OutOfBounds 에러가 백준 서버에서 발생했습니다. (이거때문에 한시간 이상은 날렸습니다.) vector로 변경하여 해결되었습니다.