느낀점 및 설명 ¶
하루종일 루니아만 했다아아아..ㅠ.ㅜ 너무 게으른거아냐?? 이거 문제있는데.. '게으름 유전자' 가 들어있는건가..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; } }