#include #include #include using namespace std; // east west south north 1 2 3 4 // 백트래킹 // 첫 백트래킹에서 방향 파악하고 그 방향 = 머리 방향 // 마지막 백트래킹에서 방향 파악하고 그 방향 = 머리 방향 // 그 외에서는 방향이 몇 번 변하나 파악 vector> factoryMap; vector dirOfRobot; int dx[4] = { 0, 0, 1, -1 }; int dy[4] = { 1, -1, 0, 0 }; int dirTransform(int dir, int idx) { if (dir == 1) { // dir = 1일 때는 1 3 4 2 if (idx == 0) return 1; else if (idx == 1) return 3; else if (idx == 2) return 4; else if (idx == 3) return 2; } else if (dir == 2) { // dir = 2일 때는 2 3 4 1 if (idx == 0) return 2; else if (idx == 1) return 3; else if (idx == 2) return 4; else if (idx == 3) return 1; } else if (dir == 3) { // dir = 3일 때는 3 1 2 4 if (idx == 0) return 3; else if (idx == 1) return 1; else if (idx == 2) return 2; else if (idx == 3) return 4; } else if (dir == 4) { // dir = 4일 때는 4 1 2 3 if (idx == 0) return 4; else if (idx == 1) return 1; else if (idx == 2) return 2; else if (idx == 3) return 3; } } bool endOfDFS = false; void printFactoryMap() { for (const auto& row : factoryMap) { for (int cell : row) { cout << cell << " "; // 각 요소를 출력 } cout << endl; // 한 줄 끝날 때마다 줄 바꿈 } } int BFS(pair currPos, pair targetPos, vector> visited) { queue> Q; Q.push(currPos); int cnt = 1; visited[currPos.first][currPos.second] = cnt + 1; while (!Q.empty()) { int currX = Q.front().first; int currY = Q.front().second; cnt = visited[currX][currY]; if (Q.front() == targetPos) break; Q.pop(); for (int i = 0; i < 4; i++) { int nx = currX + dx[i]; int ny = currY + dy[i]; if (visited[nx][ny] == 1) { visited[nx][ny] = cnt + 1; Q.push(make_pair(nx, ny)); } } } return cnt - 2; } void DFS(int numOfMove, int maxMove, pair currPos, pair targetPos, int currDir) { if (numOfMove > maxMove) return; int currX = currPos.first; int currY = currPos.second; factoryMap[currX][currY] = numOfMove + 1; if (currPos == targetPos) { endOfDFS = true; dirOfRobot.push_back(currDir); //cout << "현재 좌표: (" << currX << ", " << currY << ")\n"; return; } for (int i = 0; i < 4; i++) { int j = dirTransform(currDir, i); int nx = currX + dx[j - 1]; int ny = currY + dy[j - 1]; //cout << "현재 좌표: (" << currX << ", " << currY << ")" << currDir << "= 현재 방향" << numOfMove << "\n"; if (factoryMap[nx][ny] == 1 || factoryMap[nx][ny] > numOfMove + 1) { //cout << "현재 탐색 중인 좌표: (" << nx << ", " << ny << ")" << currDir << "= 현재 방향" << numOfMove << "\n"; //printFactoryMap(); DFS(numOfMove + 1, maxMove, make_pair(nx, ny), targetPos, j); if (endOfDFS == true) { //cout << "현재 좌표: (" << currX << ", " << currY << ")\n"; dirOfRobot.push_back(currDir); return; } } } } int main() { int N, M; cin >> N >> M; factoryMap.assign(N + 2, vector(M + 2, 0)); //visitedMap.assign(N + 2, vector(M + 2, false)); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { int tmp; cin >> tmp; factoryMap[i][j] = (tmp + 1) % 2; // 0, 1 반전 } } pair startPos, targetPos; int startDir, targetDir; cin >> startPos.first >> startPos.second >> startDir >> targetPos.first >> targetPos.second >> targetDir; DFS(0, BFS(startPos, targetPos, factoryMap), startPos, targetPos, startDir); //cout << DFS(startPos, targetPos, startDir); int size = dirOfRobot.size(); int numOfRotation = 0; int numOfCommand = 0; int cntGok = 2; //cout << numOfCommand << "\n"; for (int i = 1; i < size; i++) { if (dirOfRobot[i] != dirOfRobot[i - 1]) { numOfRotation++; cntGok = 2; } else { cntGok--; } if (cntGok == -1) { //cout << "얍"; numOfCommand += 1; cntGok = 2; } } //cout << numOfCommand << "\n"; numOfCommand += numOfRotation * 2; //cout << numOfCommand << "\n"; if (dirOfRobot[0] != targetDir) { if (dirOfRobot[0] * targetDir == 2 || dirOfRobot[0] * targetDir == 12) { numOfCommand += 2; } else { numOfCommand += 1; } } //cout << numOfCommand << "\n"; if (size != 1) { if (dirOfRobot[size - 2] == startDir || (dirOfRobot[size - 2] * startDir == 2) || (dirOfRobot[size - 2] * startDir == 12)) { numOfCommand += 1; } } cout << numOfCommand; return 0; }

제출 #128880

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: