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++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.