C++ Tikus dalam labirin membenarkan berbilang langkah atau lompatan

Diberi n*n grid maze. Tetikus kami muncul di sudut kiri atas grid. Kini tetikus hanya boleh bergerak ke bawah atau ke hadapan, dan dalam varian ini tetikus boleh membuat lompatan berbilang jika dan hanya jika blok itu kini mempunyai nilai bukan sifar. Lompatan maksimum yang boleh dilakukan tetikus daripada sel semasa ialah nombor yang terdapat dalam sel, kini tugas anda adalah untuk mengetahui sama ada tetikus boleh mencapai sudut kanan bawah grid, contohnya -

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

Cari penyelesaiannya

di sini Dalam pendekatan ini, kami akan menggunakan penjejakan ke belakang untuk menjejaki setiap laluan yang boleh diambil oleh tetikus sekarang. Jika tetikus mencapai destinasinya dari mana-mana laluan, kami kembali benar untuk laluan itu dan kemudian mencetak laluan itu. Jika tidak, kami mencetak bahawa laluan itu tidak wujud.

Contoh

 
#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

Penjelasan kod di atas

Dalam kaedah di atas, kami menyemak setiap laluan yang boleh dijana daripada sel semasa, sambil menyemak, kami kini menandakan laluan sebagai satu. Apabila jalan kita menemui jalan buntu, kita memeriksa sama ada jalan buntu itu adalah destinasi kita. Sekarang, jika itu bukan destinasi kami, kami mundur, dan apabila kami mundur, kami menandakan sel sebagai 0 kerana laluan itu tidak sah, dan begitulah cara kod kami mengendalikannya.

Kesimpulan

Dalam tutorial ini kami akan menyelesaikan masalah tetikus dalam labirin, membenarkan beberapa langkah atau lompatan. Kami juga mempelajari program C++ untuk masalah ini dan kaedah lengkap (generik) untuk menyelesaikannya. Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami harap anda mendapati tutorial ini membantu.

Atas ialah kandungan terperinci C++ Tikus dalam labirin membenarkan berbilang langkah atau lompatan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!