[코드트리]메이즈 러너 2%실패

M명의 참가자가 미로 탈출하기 게임에 참가하였습니다.

미로의 구성은 다음과 같습니다.

1. 미로는 N×N 크기의 격자입니다. 각 위치는 (r,c)의 형태로 표현되며, 아래로 갈수록 r이 증가, 오른쪽으로 갈수록 c가 증가합니다. 좌상단은 (1,1)입니다.
2. 미로의 각 칸은 다음 3가지 중 하나의 상태를 갖습니다.
   1. 빈 칸
      • 참가자가 이동 가능한 칸입니다.
   2. 벽
      • 참가자가 이동할 수 없는 칸입니다.
      • 1이상 9이하의 내구도를 갖고 있습니다.
      • 회전할 때, 내구도가 1씩 깎입니다.
      • 내구도가 0이 되면, 빈 칸으로 변경됩니다.
   3. 출구
      • 참가자가 해당 칸에 도달하면, 즉시 탈출합니다.

1초마다 모든 참가자는 한 칸씩 움직입니다. 움직이는 조건은 다음과 같습니다.

• 두 위치 (x1,y1), (x2,y2)의 최단거리는 ∣x1−x2∣+∣y1−y2∣로 정의됩니다.
• 모든 참가자는 동시에 움직입니다.
• 상하좌우로 움직일 수 있으며, 벽이 없는 곳으로 이동할 수 있습니다.
• 움직인 칸은 현재 머물러 있던 칸보다 출구까지의 최단 거리가 가까워야 합니다.
• 움직일 수 있는 칸이 2개 이상이라면, 상하로 움직이는 것을 우선시합니다.
• 참가가가 움직일 수 없는 상황이라면, 움직이지 않습니다.
• 한 칸에 2명 이상의 참가자가 있을 수 있습니다.

모든 참가자가 이동을 끝냈으면, 다음 조건에 의해 미로가 회전합니다.

• 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 잡습니다.
• 가장 작은 크기를 갖는 정사각형이 2개 이상이라면, 좌상단 r 좌표가 작은 것이 우선되고, 그래도 같으면 c 좌표가 작은 것이 우선됩니다.
• 선택된 정사각형은 시계방향으로 90도 회전하며, 회전된 벽은 내구도가 1씩 깎입니다.

K초 동안 위의 과정을 계속 반복됩니다. 만약 K초 전에 모든 참가자가 탈출에 성공한다면, 게임이 끝납니다. 게임이 끝났을 때, 모든 참가자들의 이동 거리 합과 출구 좌표를 출력하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 N, M, K가 공백을 사이에 두고 주어집니다.

다음 N개의 줄에 걸쳐서 N×N 크기의 미로에 대한 정보가 주어집니다.

• 0이라면, 빈 칸을 의미합니다.
• 1이상 9이하의 값을 갖는다면, 벽을 의미하며, 해당 값은 내구도를 뜻합니다.

다음 M개의 줄에 걸쳐서 참가자의 좌표가 주어집니다. 모든 참가자는 초기에 빈 칸에만 존재합니다.

다음 줄에 출구의 좌표가 주어집니다. 출구는 빈 칸에만 주어집니다.

• N: 미로의 크기 (4≤N≤10)
• M: 참가자 수 (1≤M≤10)
• K: 게임 시간 (1≤K≤100)

출력 형식

게임 시작 후 K초가 지났거나, 모든 참가자가 미로를 탈출했을 때, 모든 참가자들의 이동 거리 합과 출구 좌표를 출력합니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <numeric>
#include <map>
#include <cmath>
using namespace std;

int M, N, K, ret;
vector<vector<int>> maze;		//0 : 빈칸, 1~9 : 벽내구도
vector<vector<int>> mazeMember;		//-1 : nothing, 0~10 : participant
pair<int, int> exitL;
vector<pair<int, int>> ptcp;
vector<bool> endFlag;

#define diff(x1,y1,x2,y2) abs(x1-x2) + abs(y1-y2)

int _y[] = { -1,1,0,0 };		//상 하 좌 우
int _x[] = { 0,0,-1,1 };

void printMaze(vector<vector<int>> v)
{
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j < v.size(); j++)
		{
			cout << v[i][j] << "	";
		}cout << endl;
	}cout << endl;
}

void movePtcp()
{
	for (int m = 0; m < M; m++)
	{
		if (endFlag[m]) continue;	//already exit
		int min = 21;
		pair<int, int> moveLocation = ptcp[m];

		int sy = ptcp[m].first, sx = ptcp[m].second;
		int nDiff = diff(sy, sx, exitL.first, exitL.second);

		for (int dir = 0; dir < 4; dir++)
		{
			int ny = sy + _y[dir], nx = sx + _x[dir];
			if (ny >= N || nx >= N || ny < 0 || nx < 0)  continue;	//out
			if (maze[ny][nx]>0) continue;	//wall
			
			int diffDis = diff(ny, nx, exitL.first, exitL.second);
			if (diffDis < min && diffDis < nDiff)
			{
				moveLocation = make_pair(ny, nx);
				min = diffDis;
			}

		}

		//success to exit
		if (moveLocation == exitL)
		{
			mazeMember[sy][sx] -= pow(2, m);
			ptcp[m] = moveLocation;
			endFlag[m] = true;
			ret++;
		}

		if (moveLocation != ptcp[m])
		{
			mazeMember[sy][sx] -= pow(2, m);
			mazeMember[moveLocation.first][moveLocation.second] += pow(2, m);
			ptcp[m] = moveLocation;
			ret++;
		}
		cout << "move " << m << endl;
		printMaze(mazeMember);
		
	}
}

bool cmp(pair<int, int>& a, pair<int, int>& b)
{
	if (a.second == b.second)
	{
		if (ptcp[a.first].first == ptcp[b.first].first)
			return ptcp[a.first].second < ptcp[b.first].second;
		return ptcp[a.first].first < ptcp[b.first].first;
	}
	return a.second < b.second;
}

pair<int, pair<int,int>> selectrecInfo()
{
	vector<pair<int, int>> nearer;
	for (int m = 0; m < M; m++)
	{
		if (endFlag[m]) continue;
		int diffDis = diff(ptcp[m].first, ptcp[m].second, exitL.first, exitL.second);
		nearer.push_back(make_pair(m, diffDis));
	}
	sort(nearer.begin(), nearer.end(), cmp);
	
	pair<int, int> boxPtcp = ptcp[nearer.front().first];	//포함될 참가자 좌표
	int n = abs(boxPtcp.first - exitL.first) > abs(boxPtcp.second - exitL.second) ? abs(boxPtcp.first - exitL.first) + 1 : abs(boxPtcp.second - exitL.second) + 1;	//박스 길이

	//위 > 왼 > 좌 > 우
	pair<int, int> upoint, dpoint, lpoint, rpoint;
	if (boxPtcp.first < exitL.first)
	{
		upoint = boxPtcp, dpoint = exitL;
	}
	else if ((boxPtcp.first > exitL.first))
	{
		upoint = exitL, dpoint = boxPtcp;
	}
	else
	{
		if (boxPtcp.second < exitL.second)
		{
			upoint = boxPtcp, upoint = exitL;
		}
		else upoint = exitL, upoint = boxPtcp;;
	}

	if (boxPtcp.second < exitL.second)
	{
		lpoint = boxPtcp, rpoint = exitL;
	}
	else if ((boxPtcp.second > exitL.second))
	{
		lpoint = exitL, rpoint = boxPtcp;
	}
	else
	{
		if (boxPtcp.first < exitL.first)
		{
			lpoint = boxPtcp, rpoint = exitL;
		}
		else lpoint = exitL, rpoint = boxPtcp;;
	}
	
	for (int y = dpoint.first - n + 1; y <= upoint.first + n - 1; y++) {
		for (int x = rpoint.second - n + 1; x <= lpoint.second + n - 1; x++)
		{
			//cout << "(y,x) : " << y << ", " << x << endl;
			if (y < 0 || y >= N || x < 0 || x >= N) continue;
			return make_pair(n, make_pair(y, x));
		}
	}

}

void turn90(vector<vector<int>>& v)
{
	int n = v.size();
	vector < vector<int>> tmp(N, vector<int>(N, 0));
	tmp = v;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < n - i; j++)
		{
			tmp[j][n - 1 - i] = v[i][j];
			tmp[n-1-j][i] = v[n-1-i][n-1-j];
		}
	}
	//printMaze(tmp);
	v = tmp;
}

vector<int> findPtcp(long long value)
{
	vector<int> members;
	if (value == 0) return members;
	if (value == 1)
	{
		members.push_back(0);
		return members;
	}
	int cnt = 0;

	while (value != 0)
	{
		if (value & 0b0000000001) members.push_back(cnt);
		value = value >> 1;
		cnt++;
	}

	return members;
}


int main()
{
	
	cin >> N >> M >> K;
	maze.resize(N, vector<int>(N));
	endFlag.resize(N, false);
	mazeMember.resize(N, vector<int>(N, 0));

	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++) cin >> maze[y][x];

	for (int m = 0; m < M; m++)
	{
		int y, x;
		cin >> y >> x;
		ptcp.push_back(make_pair(y-1, x-1));
		mazeMember[y-1][x-1] += pow(2, m);
	}

	int exitY, exitX;
	cin >> exitY >> exitX;
	exitL.first = exitY - 1, exitL.second = exitX - 1;
	maze[exitL.first][exitL.second] = -1;

	cout << "maze===========" << endl;
	printMaze(maze);
	cout << "mazeMember===========" << endl;
	printMaze(mazeMember);

	while (K--) {
		movePtcp();
		if (accumulate(endFlag.begin(), endFlag.end(), 0) == -1 * M) break;		// everyone is exited

		pair<int, pair<int, int>> recInfo = selectrecInfo();
		//cout << recInfo.first << "/ " << recInfo.second.first << ", " << recInfo.second.second << endl;

		vector<vector<int>> rec(recInfo.first, vector<int>(recInfo.first, 0));
		vector<vector<int>> recMem(recInfo.first, vector<int>(recInfo.first, 0));

		for (int y = 0; y < recInfo.first; y++)
			for (int x = 0; x < recInfo.first; x++) {
				rec[y][x] = maze[recInfo.second.first + y][recInfo.second.second + x];
				recMem[y][x] = mazeMember[recInfo.second.first + y][recInfo.second.second + x];
			}

		turn90(rec);
		turn90(recMem);

		for (int y = 0; y < recInfo.first; y++) {
			for (int x = 0; x < recInfo.first; x++) {
				maze[recInfo.second.first + y][recInfo.second.second + x] = rec[y][x];
				if (rec[y][x] > 0) maze[recInfo.second.first + y][recInfo.second.second + x]--;
				if (rec[y][x] == -1) exitL = make_pair(y + recInfo.second.first, x + recInfo.second.second);
				mazeMember[recInfo.second.first + y][recInfo.second.second + x] = recMem[y][x];
			}
		}
		cout << "maze===========" << endl;
		printMaze(maze);
		cout << "mazeMember===========" << endl;
		printMaze(mazeMember);

		for (int y = 0; y < recInfo.first; y++) {
			for (int x = 0; x < recInfo.first; x++) {
				vector<int> mems = findPtcp(recMem[y][x]);
				for (int mem : mems)
				{
					ptcp[mem] = make_pair(y + recInfo.second.first, x + recInfo.second.second);
					//cout << "update : " << mem << " - " << y << ", " << x << endl;
				}
			}
		}
	}
	cout << ret << endl;
	cout << exitL.first + 1 << " " << exitL.second + 1 << endl;

}