여러 단계 또는 점프를 허용하는 미로의 C++ 쥐

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를 반환한 다음 해당 경로를 인쇄합니다. 그렇지 않으면 경로가 존재하지 않는다고 인쇄됩니다.

Example

 
#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&#39;t exist
                   //or the path doesn&#39;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&#39;t exist\n";
    return 0;
}

Output

1 0 0 0
1 0 0 1
0 0 0 1
0 0 0 1

위 코드 설명

위 방법에서는 현재 셀에서 생성할 수 있는 모든 경로를 확인합니다. 확인하는 동안 이제 경로를 하나로 표시합니다. 우리가 가는 길이 막다른 골목에 도달하면, 그 막다른 골목이 목적지인지 확인합니다. 이제 그것이 목적지가 아니면 역추적하고, 역추적할 때 경로가 유효하지 않기 때문에 셀을 0으로 표시합니다. 이것이 우리 코드에서 처리하는 방식입니다.

결론

이 튜토리얼에서는 여러 단계 또는 점프를 허용하여 미로에서 마우스 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이를 해결하기 위한 완전한 방법(일반)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.

위 내용은 여러 단계 또는 점프를 허용하는 미로의 C++ 쥐의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!