U E D R , A S I H C RSS
ZeroWiki

Robbery/조현태

Robbery/조현태

느낀점 및 설명

하루종일 루니아만 했다아아아..ㅠ.ㅜ 너무 게으른거아냐?? 이거 문제있는데.. '게으름 유전자' 가 들어있는건가..OTL..
... 뭐 그래도 인생은 즐기는것.. 게임좀 하면 어때~~~~ (미래에 니트족 한명 또 추가되겠군..;;)
.. 너무 놀았으니 자기전에 간단히 한개 풀어주고 자야지.. 해서 푼게 이것.
CSI를 많이 봐서 그런지 형사아저씨를 돕고싶었나보다.^^

주어진 예제와 그 이외의 몇몇 사항을 바탕으로 테스트를 하였다.
경우의 수가 여러가지 나오는 경우를 어떻게 처리할까 고민했는데.. 못찾은 걸로 할까? 아니면 답으로 간주해서 출력할까? 하다가, 이 경우는 못찾은 걸로 처리하였다. ( "Nothing known." 으로 출력된다. )
'명확한 경우' 에 속하지 않기때문에..^^
최적화를 아예 안할까 하다가.. 그럼 너무너무 간단해져서 약간이나마 최적화를 했다.

자전거 문제에 이 소스를 배껴넣다가.. 규칙을 일부 잘못 이해한것 같아서 수정했다.
이전의 경우 도둑이 특정시간에 존재할 수 없는경우 "The robber has escaped." 를 출력했으나, 지금은 모든 시간의 움직임을 고려해서 존재하지 않으면 "The robber has escaped."를 출력하도록 수정하였다. (사실 소스상에선 그다지 바뀐건 없다..^^)

소스 


~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;
	}
}
----
Robbery
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:27:55
Processing time 0.0375 sec