[PS][시뮬레이션][이동시키기]/[BOJ][17837][새로운 게임2]

boj17837.cpp

//5:50 -
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int n, k;
int map[13][13];
//우 좌 위 아래
int dx[4] = { 0,0,-1, 1 };
int dy[4] = { 1,-1,0,0 };
int nextdir[4] = { 1,0,3,2 };
struct horse {
	int x, y, d;
	horse(int _x=0, int _y=0, int _d=0) : x(_x), y(_y), d(_d) {
		//empty;
	}
};

horse arr[11]; //말의 정보
queue<int> entry[13][13]; //말이 위치한 좌표
int ans = 0;


bool in_range(int x, int y) {
	return 0 <= x && 0 <= y && x < n && y < n;
}

bool game_end(int x, int y) {
	return entry[x][y].size() >= 4;
}

void horse_show(int h) {
	//cout << h << ": (" << arr[h].x << "," << arr[h].y <<","<<arr[h].d<<")\n";
}

bool horse_move(int h, int blue) {
	horse_show(h);
	stack<int> stck;
	int x = arr[h].x;
	int y = arr[h].y;
	int d = arr[h].d;
	int nx, ny,i,j, loop;
	nx = x + dx[d];
	ny = y + dy[d];
	

	if (!in_range(nx, ny) || map[nx][ny] == 2) { //파랑
		if (!blue) {
			d = nextdir[d];
			arr[h].d = d;
			return horse_move(h, 1);
		}
		else {
			//가만히 있는다.
			return false;
		}
	}
	else if (map[nx][ny] == 1) { //빨강
		//가장 앞에꺼가 h가 되도록 한다.
		for (i = 0; i < entry[x][y].size(); i++) {
			if (entry[x][y].front() == h) {
				break;
			}
			else {
				entry[x][y].push(entry[x][y].front());
				entry[x][y].pop();
			}
		}
		//i개만큼 entry[x][y] -> entry[nx][ny] 단 stack에 넣어서 순서 반대로
		loop = entry[x][y].size() - i;
		//stack에 넣었다가 빨간색으로 옮긴다. 
		for (j = 0; j < loop; j++) {
			arr[entry[x][y].front()].x = nx;
			arr[entry[x][y].front()].y = ny;
			stck.push(entry[x][y].front());
			entry[x][y].pop();
		}
		while (!stck.empty()) {
			entry[nx][ny].push(stck.top());
			if (game_end(nx, ny)) return true;
			stck.pop();
		}
	}
	else {//하양
		//가장 앞에꺼가 h가 되도록 한다.
		for (i = 0; i < entry[x][y].size(); i++) {
			if (entry[x][y].front() == h) {
				break;
			}
			else {
				entry[x][y].push(entry[x][y].front());
				entry[x][y].pop();
			}
		}
		//i개만큼 entry[x][y] -> entry[nx][ny] 단 stack에 넣어서 순서 반대로
		loop = entry[x][y].size() - i;
		for (j = 0; j <loop; j++) {
			//바로 흰색으로 옮긴다. 
			arr[entry[x][y].front()].x = nx;
			arr[entry[x][y].front()].y = ny;
			entry[nx][ny].push(entry[x][y].front());
			if (game_end(nx, ny)) return true;
			entry[x][y].pop();
		}
	}
	horse_show(h);
	return false;
}


int solve(void) {
	while (true) {
		ans++;
		//cout << "game " << ans << "\n";
		if (ans > 1000) return -1;
		for (int h = 0; h < k; h++) {
			if (horse_move(h, 0)) {
				return ans;
			}
		}
	}
	return -1;
}

int main(void) {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < k; i++) {
		int x, y, d;
		cin >> x >> y >> d;
		arr[i] = { x - 1, y - 1,d - 1 };
		entry[x - 1][y - 1].push(i);
	}

	cout << solve() << "\n";
	return 0;
}