느낀점 및 설명 ¶
하루종일 루니아만 했다아아아..ㅠ.ㅜ 너무 게으른거아냐?? 이거 문제있는데.. '게으름 유전자' 가 들어있는건가..OTL..
... 뭐 그래도 인생은 즐기는것.. 게임좀 하면 어때~~~~ (미래에 니트족 한명 또 추가되겠군..;;)
.. 너무 놀았으니 자기전에 간단히 한개 풀어주고 자야지.. 해서 푼게 이것.
CSI를 많이 봐서 그런지 형사아저씨를 돕고싶었나보다.^^
... 뭐 그래도 인생은 즐기는것.. 게임좀 하면 어때~~~~ (미래에 니트족 한명 또 추가되겠군..;;)
.. 너무 놀았으니 자기전에 간단히 한개 풀어주고 자야지.. 해서 푼게 이것.
CSI를 많이 봐서 그런지 형사아저씨를 돕고싶었나보다.^^
주어진 예제와 그 이외의 몇몇 사항을 바탕으로 테스트를 하였다.
경우의 수가 여러가지 나오는 경우를 어떻게 처리할까 고민했는데.. 못찾은 걸로 할까? 아니면 답으로 간주해서 출력할까? 하다가, 이 경우는 못찾은 걸로 처리하였다. ( "Nothing known." 으로 출력된다. )
'명확한 경우' 에 속하지 않기때문에..^^
최적화를 아예 안할까 하다가.. 그럼 너무너무 간단해져서 약간이나마 최적화를 했다.
경우의 수가 여러가지 나오는 경우를 어떻게 처리할까 고민했는데.. 못찾은 걸로 할까? 아니면 답으로 간주해서 출력할까? 하다가, 이 경우는 못찾은 걸로 처리하였다. ( "Nothing known." 으로 출력된다. )
'명확한 경우' 에 속하지 않기때문에..^^
최적화를 아예 안할까 하다가.. 그럼 너무너무 간단해져서 약간이나마 최적화를 했다.
자전거 문제에 이 소스를 배껴넣다가.. 규칙을 일부 잘못 이해한것 같아서 수정했다.
이전의 경우 도둑이 특정시간에 존재할 수 없는경우 "The robber has escaped." 를 출력했으나, 지금은 모든 시간의 움직임을 고려해서 존재하지 않으면 "The robber has escaped."를 출력하도록 수정하였다. (사실 소스상에선 그다지 바뀐건 없다..^^)
이전의 경우 도둑이 특정시간에 존재할 수 없는경우 "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;
}
}
