Robbery/조현태

������ ¶

~cpp
#include <iostream>
#include <Windows.h>
#include <vector>
#include <algorithm>
#include <atltypes.h>

using namespace std;

#define CAN_MOVE_POINT 0
#define DONT_MOVE_POINT 1

vector< vector< vector<int> > > g_cityMap;
vector< vector<POINT> > g_canMovePoints;
vector<int> g_saveMessageTime;
vector< vector<POINT> > g_maxPoints;

void InitCityMap(int cityWidth, int cityHeight, int keepTime)
{
	g_maxPoints.clear();
	g_saveMessageTime.clear();
	g_canMovePoints.clear();
	g_cityMap.clear();

	g_canMovePoints.resize(keepTime);
	g_cityMap.resize(keepTime);
	for (register int i = 0; i < (int)g_cityMap.size(); ++i)
	{
		g_cityMap[i].resize(cityWidth);
		for(register int j = 0; j < (int)g_cityMap[i].size(); ++j)
		{
			g_cityMap[i][j].resize(cityHeight);
		}
	}
}

void SetMessagePoints(int receiveTime, int left, int top, int right, int bottom)
{
	for (register int i = left - 1; i < right; ++i)
	{
		for (register int j = top - 1; j < bottom; ++j)
		{
			g_cityMap[receiveTime - 1][i][j] = DONT_MOVE_POINT;
		}
	}
}

void SetCanMovePoints()
{
	for (register int i = 0; i < (int)g_cityMap.size(); ++i)
	{
		for(register int j = 0; j < (int)g_cityMap[i].size(); ++j)
		{
			for(register int k = 0; k < (int)g_cityMap[i][j].size(); ++k)
			{
				if (CAN_MOVE_POINT == g_cityMap[i][j][k])
				{
					POINT canMovePoint;
					canMovePoint.x = j;
					canMovePoint.y = k;
					g_canMovePoints[i].push_back(canMovePoint);
				}
			}
		}
	}
}

void MoveNextPoint(POINT nowPoint, POINT targetPoint, int nowTime, int targetTime, vector<POINT>& movedPoint)
{
	//// ������할 ��� ������ ��������� ////
	if (0 > nowPoint.x || (int)g_cityMap[nowTime].size() <= nowPoint.x)
		return;
	if (0 > nowPoint.y || (int)g_cityMap[nowTime][nowPoint.x].size() <= nowPoint.y)
		return;
	if (DONT_MOVE_POINT == g_cityMap[nowTime][nowPoint.x][nowPoint.y])
		return;

	//// ���표��������� ������했������ ////
	if (nowTime == targetTime)
	{
		//// ���표��������� ��������� ////
		if (nowPoint.x != targetPoint.x || nowPoint.y != targetPoint.y)
			return;

		int suchTime = -1;
		for (register int i = 0; i < (int)g_saveMessageTime.size(); ++i)
		{
			if (nowTime < g_saveMessageTime[i])
			{
				suchTime = g_saveMessageTime[i];
			}
		}
		//// ��������� ������������ ��������� ��������� ////
		if (-1 == suchTime)
		{
			movedPoint.push_back(nowPoint);
			g_maxPoints.push_back(movedPoint);
			movedPoint.pop_back();
			return;
		}

		//// ������������ ��������� ��������� ////
		for (register int i = 0; i < (int)g_canMovePoints[suchTime].size(); ++i)
		{
			MoveNextPoint(nowPoint, g_canMovePoints[suchTime][i], nowTime, suchTime, movedPoint);
		}
		return;
	}

	//// ������������ ��������� ////
	int movingTimeX = targetPoint.x - nowPoint.x;
	int movingTimeY = targetPoint.y - nowPoint.y;
	if (abs(movingTimeX) + abs(movingTimeY) > targetTime - nowTime)
		return;
	else
	{
		movedPoint.push_back(nowPoint);
		POINT tempPoint = nowPoint;
		if (0 < movingTimeX)
		{
			++nowPoint.x;
			MoveNextPoint(nowPoint, targetPoint, nowTime + 1, targetTime, movedPoint);
		}
		else if (0 > movingTimeX)
		{
			--nowPoint.x;
			MoveNextPoint(nowPoint, targetPoint, nowTime + 1, targetTime, movedPoint);
		}
		nowPoint = tempPoint;

		if (0 < movingTimeY)
		{
			++nowPoint.y;
			MoveNextPoint(nowPoint, targetPoint, nowTime + 1, targetTime, movedPoint);
		}
		else if (0 > movingTimeY)
		{
			--nowPoint.y;
			MoveNextPoint(nowPoint, targetPoint, nowTime + 1, targetTime, movedPoint);
		}
		nowPoint = tempPoint;

		//// ���표������������ ��������� ��������� ��������� ////
		if (abs(movingTimeX) + abs(movingTimeY) < targetTime - nowTime)
		{
			const int ADD_POINT_X[5] = {0, +1, -1, 0, 0};
			const int ADD_POINT_Y[5] = {0, 0, 0, +1, -1};
			for (register int i = 0; i < 5; ++i)
			{
				nowPoint.x += ADD_POINT_X[i];
				nowPoint.y += ADD_POINT_Y[i];
				MoveNextPoint(nowPoint, targetPoint, nowTime + 1, targetTime, movedPoint);
				nowPoint = tempPoint;
			}
		}
		movedPoint.pop_back();
	}
}

void KillSameThing()
{
	for (register int i = 0; i < (int)g_maxPoints.size(); ++i)
	{
		for (register int j = i + 1; j < (int)g_maxPoints.size(); ++j)
		{
			bool isSame = TRUE;
			for (register int k = 0; k < (int)g_maxPoints[i].size(); ++k)
			{
				if (g_maxPoints[i][k].x != g_maxPoints[j][k].x || g_maxPoints[i][k].y != g_maxPoints[j][k].y)
				{
					isSame = FALSE;
					break;
				}
			}
			if (isSame)
			{
				g_maxPoints.erase(g_maxPoints.begin() + j);
				--i;
				break;
			}
		}
	}
}

void main()
{
	for (int testCaseNumber = 1; ; ++testCaseNumber)
	{
		int cityWidth, cityHeight, keepTime;
		scanf("%d %d %d", &cityWidth, &cityHeight, &keepTime);

		if (0 == cityWidth && 0 == cityHeight && 0 == keepTime)
			break;

		InitCityMap(cityWidth, cityHeight, keepTime);

		int numberOfMessage;
		scanf("%d", &numberOfMessage);

		int receiveTime, left, top, right, bottom;
		for (register int i = 0; i < numberOfMessage; ++i)
		{
			scanf("%d %d %d %d %d", &receiveTime, &left, &top, &right, &bottom);
			SetMessagePoints(receiveTime, left, top, right, bottom);
			if (g_saveMessageTime.end() == find(g_saveMessageTime.begin(), g_saveMessageTime.end(), receiveTime - 1))
				g_saveMessageTime.push_back(receiveTime - 1);
		}
		SetCanMovePoints();
		bool isEscaped = FALSE;
		for (register int i = 0; i < keepTime; ++i)
		{
			if (0 == g_canMovePoints[i].size())
			{
				isEscaped = TRUE;
			}
		}
		for (register int i = 0; i < (int)g_canMovePoints[0].size(); ++i)
		{
			vector<POINT> movedPoint;
			MoveNextPoint(g_canMovePoints[0][i], g_canMovePoints[0][i], 0, 0, movedPoint);
		}
		KillSameThing();
		cout << "Robbery #" << testCaseNumber << ":" << endl;
		if (0 == g_maxPoints.size() && 0 != g_saveMessageTime.size())
		{
			cout << "The robber has escaped." << endl;
		}
		else if (1 == g_maxPoints.size() && keepTime == g_maxPoints[0].size() + 1)
		{
			for (register int i = 0; i < (int)g_maxPoints[0].size(); ++i)
			{
				cout << "Time step " << i + 1 << ": The robber has been at " << g_maxPoints[0][i].x + 1 << "," << g_maxPoints[0][i].y + 1 << "." << endl;
			}
		}
		else
		{
			cout << "Nothing known." << endl;
		}
		cout << endl;
	}
}