Cho một mê cung lưới n * n. Con chuột của chúng ta hiện diện ở góc trên cùng bên trái của lưới. Bây giờ chuột chỉ có thể di chuyển xuống hoặc chuyển tiếp, và nếu và chỉ khi khối có giá trị khác 0 đối với nó bây giờ trong biến thể này, chuột được phép có nhiều bước nhảy. Bước nhảy tối đa mà con chuột có thể thực hiện từ ô hiện tại là số có trong ô và bây giờ bạn có nhiệm vụ tìm xem con chuột có thể đến góc dưới cùng bên phải của lưới không, chẳng hạn -
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 Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng tôi sẽ sử dụng backtracking để theo dõi mọi con đường mà chuột có thể đi ngay bây giờ. Nếu con chuột đến đích của chúng ta từ bất kỳ đường dẫn nào, chúng ta trả về true cho đường dẫn đó và sau đó in đường dẫn. Nếu không, chúng tôi cho rằng đường dẫn không tồn tại.
Ví dụ
#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;
} Đầu ra
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
Giải thích về Quy tắc trên
Trong cách tiếp cận ở trên, chúng tôi kiểm tra mọi đường dẫn mà nó có thể tạo ra từ ô hiện tại của chúng tôi và trong khi kiểm tra điều đó, chúng tôi đánh dấu các đường dẫn là một ngay bây giờ. Khi con đường của chúng ta đi đến ngõ cụt, chúng ta kiểm tra xem ngõ cụt đó có phải là đích đến của chúng ta hay không. Bây giờ, nếu đó không phải là điểm đến của chúng tôi, chúng tôi quay lại và khi quay lại, chúng tôi đánh dấu ô là 0 vì đường dẫn này không hợp lệ và đây là cách mã của chúng tôi tiếp tục.
Kết luận
Trong hướng dẫn này, chúng tôi giải bài Rat in a Maze với nhiều bước hoặc cho phép nhảy. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.