#include #include #include #include using namespace std; // east west south north 1 2 3 4 typedef struct _positionAndDirection { int x; int y; int dir; int kOfGok; }PosNDir; vector> factoryMap; vector>> minCmdMap; int dx[4] = { 0, 0, 1, -1 }; int dy[4] = { 1, -1, 0, 0 }; void BFS(pair targetPos, pair currPos, int currDir) { pair startPos = currPos; int currX = startPos.first; int currY = startPos.second; queue Q; Q.push(PosNDir({ currX, currY, currDir, 0 })); minCmdMap[currDir][currX][currY] = 0; while (!Q.empty()) { currX = Q.front().x; currY = Q.front().y; currDir = Q.front().dir; int currK = Q.front().kOfGok; Q.pop(); if (startPos == targetPos) continue; for (int i = 0; i < 4; i++) { int nx = currX + dx[i]; int ny = currY + dy[i]; int commands; int k = 1; if (currDir * (i + 1) == 2 || currDir * (i + 1) == 12) // 180도 회전 후 이동 (처음에만 허용) { if (make_pair(currX, currY) != startPos) continue; commands = minCmdMap[currDir][currX][currY] + 3; } else if (currDir == i + 1) // 무회전 이동 { if (currK == 3) { commands = minCmdMap[currDir][currX][currY] + 1; } else if (currK == 0) { commands = minCmdMap[currDir][currX][currY] + 1; k = currK + 1; } else { commands = minCmdMap[currDir][currX][currY]; k = currK + 1; } } else if (currDir != i + 1) // 90도 회전 후 이동 { commands = minCmdMap[currDir][currX][currY] + 2; } if (factoryMap[nx][ny] == 0 && minCmdMap[i + 1][nx][ny] > commands) { minCmdMap[i + 1][nx][ny] = commands; Q.push(PosNDir({nx, ny, i + 1, k})); } } } } int main() { int N, M; cin >> N >> M; factoryMap.assign(N + 2, vector(M + 2, 1)); minCmdMap.assign(5, (vector>(N + 2, vector(M + 2, INT_MAX)))); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { int tmp; cin >> tmp; factoryMap[i][j] = tmp; } } pair startPos, targetPos; int startDir, targetDir; cin >> startPos.first >> startPos.second >> startDir >> targetPos.first >> targetPos.second >> targetDir; BFS(targetPos, startPos, startDir); int ans = INT_MAX; for (int i = 1; i <= 4; i++) { int tmp = minCmdMap[i][targetPos.first][targetPos.second]; if (tmp == INT_MAX) continue; if (targetDir * i == 2 || targetDir * i == 12) // 180도 회전 { tmp += 2; } else if (targetDir != i + 1) // 90도 회전 { tmp += 1; } ans = min(ans, tmp); } cout << ans; return 0; }

제출 #129946

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: