Monocycle/조현태

Monocycle/조현태 ¶

느긴점 및 설명 ¶

점심에 찌게 끓이는 동안 풀려고 했다가.. 찌게를 쪼려버린 문제.ㅋ
맛있게 먹었으니 다행이지..;;;

약간~ 알고리즘의 최적화를 시켰으나.. 정답까지의 출력까지 4-5초가량 걸린다는 문제가 있었지만..
알고리즘을 수정하기 너무 귀찮았던 나머지!! 코더의 기술력으로 매꿔버린;; 엽기발랄한문제.
그래서 1초도 안걸리긴 하지만 약간의 딜레이가 눈에 보인다.ㅋ 바꿔? 말어? ㅎㅎㅎㅎ (결국 귀찮아서 때려쳤음.ㅋ)

[edit]

소스 ¶

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

using namespace std;

#define CAN_MOVE_POINT 0
#define DONT_MOVE_POINT 2
#define MOVED_POINT 1

#define MAX_X_SIZE 25

const int MOVE_PLUS_X[4] = {0, 1, 0, -1};
const int MOVE_PLUS_Y[4] = {-1, 0, 1, 0};

vector< vector<int> > g_cityMap;

struct suchPointData {
	int timeCount;
	int seePoint;
	int seeChangeCount;
	int moveDistance;
	POINT nowPoint;
};

void InitMap(int mapWidth, int mapHeight)
{
	g_cityMap.clear();

	g_cityMap.resize(mapWidth);
	for (register int i = 0; i < (int)g_cityMap.size(); ++i)
	{
		g_cityMap[i].resize(mapHeight);
	}
}

bool isInMapPoint(POINT nowPoint)
{
	if (0 <= nowPoint.x && (int)g_cityMap.size() > nowPoint.x &&
		0 <= nowPoint.y && (int)g_cityMap[nowPoint.x].size() > nowPoint.y)
		return TRUE;

	return FALSE;
}

inline int GetSurroundMovePoint(POINT suchPoint)
{
	POINT checkPoint;
	int sumOfCanMove = 0;
	for (register int i = 0; i < 4; ++i)
	{
		checkPoint.x = suchPoint.x + MOVE_PLUS_X[i];
		checkPoint.y = suchPoint.y + MOVE_PLUS_Y[i];
		if (isInMapPoint(checkPoint) && CAN_MOVE_POINT == g_cityMap[checkPoint.x][checkPoint.y])
			++sumOfCanMove;
	}
	return sumOfCanMove;
}

inline bool isCanMovePoint(POINT suchPoint, int seeWhere)
{
	POINT checkPoint;
	checkPoint.x = suchPoint.x + MOVE_PLUS_X[seeWhere];
	checkPoint.y = suchPoint.y + MOVE_PLUS_Y[seeWhere];
	if (isInMapPoint(checkPoint) && CAN_MOVE_POINT == g_cityMap[checkPoint.x][checkPoint.y])
		return TRUE;
	return FALSE;
}

int GetShortPathTime(POINT startPoint, POINT endPoint)
{
	queue<suchPointData*> suchPointDatas;

	suchPointData* startData = new suchPointData;
	startData->timeCount = 0;
	startData->seePoint = 0;
	startData->seeChangeCount = 0;
	startData->moveDistance = 0;
	startData->nowPoint = startPoint;
	suchPointDatas.push(startData);
	while(0 != suchPointDatas.size())
	{
		suchPointData* nowSuchData = suchPointDatas.front();
		suchPointDatas.pop();

		if (nowSuchData->nowPoint.x == endPoint.x && nowSuchData->nowPoint.y == endPoint.y)
		{
			if (0 == nowSuchData->moveDistance % 5)
			{
				int returnData = nowSuchData->timeCount;
				while(0 != suchPointDatas.size())
				{
					suchPointData* deleteTargetData = suchPointDatas.front();
					suchPointDatas.pop();
					delete deleteTargetData;
				}
				delete nowSuchData;
				return returnData;
			}
		}


		++nowSuchData->timeCount;
		if (0 == nowSuchData->seeChangeCount)
		{
			++nowSuchData->seeChangeCount;

			nowSuchData->seePoint = (nowSuchData->seePoint + 1) % 4;
			if (isCanMovePoint(nowSuchData->nowPoint, nowSuchData->seePoint) || 1 == GetSurroundMovePoint(nowSuchData->nowPoint))
				suchPointDatas.push(new suchPointData(*nowSuchData));

			nowSuchData->seePoint -= 2;
			if (0 > nowSuchData->seePoint)
				nowSuchData->seePoint += 4;
			if (isCanMovePoint(nowSuchData->nowPoint, nowSuchData->seePoint))
				suchPointDatas.push(new suchPointData(*nowSuchData));

			nowSuchData->seePoint = (nowSuchData->seePoint + 1) % 4;
			--nowSuchData->seeChangeCount;
		}
		else if (1 == nowSuchData->seeChangeCount)
		{
			if (1 == GetSurroundMovePoint(nowSuchData->nowPoint) || (nowSuchData->nowPoint.x == startPoint.x && nowSuchData->nowPoint.y == startPoint.y))
			{
				++nowSuchData->seeChangeCount;

				nowSuchData->seePoint = (nowSuchData->seePoint + 1) % 4;
				suchPointDatas.push(new suchPointData(*nowSuchData));

				--nowSuchData->seePoint;
				if (0 > nowSuchData->seePoint)
					nowSuchData->seePoint += 4;
				--nowSuchData->seeChangeCount;
			}
		}
		

		nowSuchData->nowPoint.x += MOVE_PLUS_X[nowSuchData->seePoint];
		nowSuchData->nowPoint.y += MOVE_PLUS_Y[nowSuchData->seePoint];

		if (isInMapPoint(nowSuchData->nowPoint) && CAN_MOVE_POINT == g_cityMap[nowSuchData->nowPoint.x][nowSuchData->nowPoint.y])
		{
			++nowSuchData->moveDistance;
			nowSuchData->seeChangeCount = 0;
			suchPointDatas.push(nowSuchData);
		}
		else
			delete nowSuchData;
	}
	return -1;
}

void main()
{
	for (int testCaseNumber = 1; ; ++testCaseNumber)
	{
		int mapWidth, mapHeight;
		scanf("%d %d", &mapHeight, &mapWidth);

		if (0 == mapWidth && 0 == mapHeight)
			break;

		InitMap(mapWidth, mapHeight);
		POINT startPoint;
		POINT endPoint;

		for (register int i = 0; i < mapHeight; ++i)
		{
			for (register int j = 0; j < mapWidth; ++j)
			{
				char mapTile = ' ';
				while (' ' == mapTile || '\n' == mapTile)
				{
					scanf("%c", &mapTile);
				}
				if ('#' == mapTile)
				{
					g_cityMap[j][i] = DONT_MOVE_POINT;
				}
				else if ('S' == mapTile)
				{
					startPoint.x = j;
					startPoint.y = i;
				}
				else if ('T' == mapTile)
				{
					endPoint.x = j;
					endPoint.y = i;
				}
			}
		}

		int calculateResult = GetShortPathTime(startPoint, endPoint);
		if (-1 == calculateResult)
		{
			cout << "destination not reachable" << endl;
		}
		else
		{
			cout << "minimum time = " << calculateResult << " sec" << endl;
		}
		cout << endl;
	}
}

----
Monocycle