n*n 격자 미로가 주어졌습니다. 마우스는 그리드의 왼쪽 상단에 나타납니다. 이제 마우스는 아래 또는 앞으로만 이동할 수 있으며, 이 변형에서는 블록의 값이 0이 아닌 경우에만 마우스가 여러 번 점프할 수 있습니다. 현재 셀에서 마우스가 할 수 있는 최대 점프는 셀에 있는 숫자입니다. 이제 여러분의 임무는 마우스가 그리드의 오른쪽 하단 모서리에 도달할 수 있는지 확인하는 것입니다. 예를 들어 -
Input : { { {1, 1, 1, 1}, {2, 0, 0, 2}, {3, 1, 0, 0}, {0, 0, 0, 1} }, Output : { {1, 1, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}, {0, 0, 0, 1} } Input : { {2, 1, 0, 0}, {2, 0, 0, 1}, {0, 1, 0, 1}, {0, 0, 0, 1} } Output: Path doesn't exist
여기 이 접근 방식에서는 역추적을 사용하여 마우스가 현재 선택할 수 있는 모든 경로를 추적합니다. 마우스가 임의의 경로에서 목적지에 도달하면 해당 경로에 대해 true를 반환한 다음 해당 경로를 인쇄합니다. 그렇지 않으면 경로가 존재하지 않는다고 인쇄됩니다.
#include <bits/stdc++.h> using namespace std; #define N 4 // size of our grid bool solveMaze(int maze[N][N], int x, int y, // recursive function for finding the path int sol[N][N]){ if (x == N - 1 && y == N - 1) { // if we reached our goal we return true and mark our goal as 1 sol[x][y] = 1; return true; } if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) { sol[x][y] = 1; // we include this index as a path for (int i = 1; i <= maze[x][y] && i < N; i++) { // as maze[x][y] denotes the number of jumps you can take //so we check for every jump in every direction if (solveMaze(maze, x + i, y, sol) == true) // jumping right return true; if (solveMaze(maze, x, y + i, sol) == true) // jumping downward return true; } sol[x][y] = 0; // if none are true then the path doesn't exist //or the path doesn't contain current cell in it return false; } return false; } int main(){ int maze[N][N] = { { 2, 1, 0, 0 }, { 3, 0, 0, 1 },{ 0, 1, 0, 1 }, { 0, 0, 0, 1 } }; int sol[N][N]; memset(sol, 0, sizeof(sol)); if(solveMaze(maze, 0, 0, sol)){ for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++) cout << sol[i][j] << " "; cout << "\n"; } } else cout << "Path doesn't exist\n"; return 0; }
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
위 방법에서는 현재 셀에서 생성할 수 있는 모든 경로를 확인합니다. 확인하는 동안 이제 경로를 하나로 표시합니다. 우리가 가는 길이 막다른 골목에 도달하면, 그 막다른 골목이 목적지인지 확인합니다. 이제 그것이 목적지가 아니면 역추적하고, 역추적할 때 경로가 유효하지 않기 때문에 셀을 0으로 표시합니다. 이것이 우리 코드에서 처리하는 방식입니다.
이 튜토리얼에서는 여러 단계 또는 점프를 허용하여 미로에서 마우스 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이를 해결하기 위한 완전한 방법(일반)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.
위 내용은 여러 단계 또는 점프를 허용하는 미로의 C++ 쥐의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!