새로운 게임 2

https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

 

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 13;
int map[MAX][MAX]; //색깔 저장
int n, k;
int answer = 0;
struct INFO { int num, x, y, dir; };
vector<INFO> horse;
vector<int> loc[MAX][MAX]; //말 위치 저장
struct MOVE { int x, y; };
MOVE mv[5] = { {0,0}, {0,1}, {0,-1}, {-1,0}, {1,0} };
bool flag = false; //말이 4개이상 쌓이면 True

void MoveWhite(int index, int dir, int x, int y) {
	int ii = horse[index].x;
	int jj = horse[index].y;

	int location=-1;
	for (int i = 0; i < loc[ii][jj].size(); i++) {
		if (loc[ii][jj][i] == horse[index].num) {
			location = i;
			break;
		}
	}
	for (int i = location; i < loc[ii][jj].size(); i++) {
		loc[x][y].push_back(loc[ii][jj][i]);
		horse[loc[ii][jj][i] - 1] = { loc[ii][jj][i] ,x,y,horse[loc[ii][jj][i]-1].dir };
	}
	loc[ii][jj].erase(loc[ii][jj].begin() + location, loc[ii][jj].end());
}

void MoveRed(int index, int dir, int x, int y) {
	int ii = horse[index].x;
	int jj = horse[index].y;

	int location=-1;
	for (int i = 0; i < loc[ii][jj].size(); i++) {
		if (loc[ii][jj][i] == horse[index].num) {
			location = i;
			break;
		}
	}
	for (int i = loc[ii][jj].size()-1; i >= location; i--) {
		loc[x][y].push_back(loc[ii][jj][i]);
		horse[loc[ii][jj][i] - 1] = { loc[ii][jj][i] ,x,y,horse[loc[ii][jj][i] - 1].dir };
	}
	loc[ii][jj].erase(loc[ii][jj].begin() + location, loc[ii][jj].end());
}

void MoveBlue(int index, int dir, int x, int y) {
	if (dir == 1)	dir = 2;
	else if (dir == 2)	dir = 1;
	else if (dir == 3)	dir = 4;
	else if (dir == 4) dir = 3;

	horse[index].dir = dir;
	int movei = horse[index].x + mv[dir].x;
	int movej = horse[index].y + mv[dir].y;

	//체스판을 벗어나는 경우
	if (movei < 1 || movei > n || movej < 1 || movej > n)
		return;

	else if (map[movei][movej] == 2)
		return;

	else if (map[movei][movej] == 0)
		MoveWhite(index, dir, movei, movej);

	else if (map[movei][movej] == 1)
		MoveRed(index, dir, movei, movej);
}

void MoveHorse(int index) {
	int currentdir = horse[index].dir;
	int movei = horse[index].x + mv[currentdir].x;
	int movej = horse[index].y + mv[currentdir].y;

	//체스판을 벗어나는 경우
	if (movei < 1 || movei > n || movej < 1 || movej > n)
		MoveBlue(index, currentdir, movei, movej);

	//흰색인 경우
	else if (map[movei][movej] == 0)
		MoveWhite(index, currentdir, movei, movej);

	else if (map[movei][movej] == 1)
		MoveRed(index, currentdir, movei, movej);

	else if (map[movei][movej] == 2)
		MoveBlue(index, currentdir, movei, movej);
}

void CheckEnd() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (loc[i][j].size() >= 4) {
				flag = true;
				break;
			}
		}
	}
}

int main(void) {
	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 1; i <= k; i++) {
		int x, y, dir;
		cin >> x >> y >> dir;

		horse.push_back({ i,x,y,dir });
		loc[x][y].push_back(i);
	}

	while (answer < 1000) {
		for (int i = 0; i < k; i++) {
			MoveHorse(i);
			CheckEnd();
			if (flag== true) {
				cout << answer+1 << endl;
				return 0;
			}
		}
		answer += 1;
	}
	cout << -1 << endl;
}