#include #include #include #include using namespace std; // east west south north 1 2 3 4 typedef struct _node { int numOfCom; int dir; int kOfGok; }node; vector> factoryMap; vector> minCommand; int dx[4] = { 0, 0, 1, -1 }; int dy[4] = { 1, -1, 0, 0 }; void printCostMap() { for (const auto& row : minCommand) { for (const node& cell : row) { // Use a reference to the node type if (cell.numOfCom == INT_MAX) cout << "M" << " "; else cout << cell.numOfCom << " "; // Print numOfCom field of the node } cout << endl; // Move to a new line after each row } cout << endl; } void BFS(pair targetPos, pair currPos, int targetDir, int currDir) { queue> Q; Q.push(currPos); minCommand[currPos.first][currPos.second].numOfCom = 0; minCommand[currPos.first][currPos.second].dir = currDir; while (!Q.empty()) { int currX = Q.front().first; int currY = Q.front().second; currDir = minCommand[currX][currY].dir; Q.pop(); //printCostMap(); //minCommand[currX][currY].dir = currDir; //if (Q.front() == targetPos) break; 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도 회전 후 이동 { commands = minCommand[currX][currY].numOfCom + 3; //k = 1; } else if (currDir == i + 1) // 무회전 이동 { if (minCommand[currX][currY].kOfGok == 3) { commands = minCommand[currX][currY].numOfCom + 1; //k = 1; } else if (minCommand[currX][currY].kOfGok == 0) { commands = minCommand[currX][currY].numOfCom + 1; k = minCommand[currX][currY].kOfGok + 1; } else { commands = minCommand[currX][currY].numOfCom; k = minCommand[currX][currY].kOfGok + 1; } } else if (currDir != i + 1) // 90도 회전 후 이동 { commands = minCommand[currX][currY].numOfCom + 2; //k = 1; } if (make_pair(nx, ny) == targetPos) { if ((i + 1) * targetDir == 2 || (i + 1) * targetDir == 12) // 180도 회전 { commands += 2; } else if ((i + 1) != targetDir) // 90도 회전 { commands += 1; } } if (factoryMap[nx][ny] == 0 && minCommand[nx][ny].numOfCom >= commands) { if (minCommand[nx][ny].numOfCom == commands && minCommand[nx][ny].kOfGok < k) continue; minCommand[nx][ny].numOfCom = commands; minCommand[nx][ny].dir = i + 1; minCommand[nx][ny].kOfGok = k; //if (make_pair(nx, ny) == targetPos) break; Q.push(make_pair(nx, ny)); } } } } int main() { int N, M; cin >> N >> M; factoryMap.assign(N + 2, vector(M + 2, 1)); minCommand.assign(N + 2, vector(M + 2, node({ INT_MAX, 0, 0 }))); 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, targetDir, startDir); int ans = minCommand[targetPos.first][targetPos.second].numOfCom; cout << ans; return 0; }

제출 #129460

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: