Chuột trong mê cung cũng là một trong những vấn đề phổ biến sử dụng backtracking. Tôi
Mê cung là một ma trận 2D, trong đó một số ô bị chặn. Một trong các ô là ô nguồn, từ đây chúng ta phải bắt đầu. Và một trong số đó là đích đến, nơi chúng ta phải đến. Chúng ta phải tìm một đường đi từ nguồn đến đích mà không di chuyển vào bất kỳ ô nào bị chặn. Hình ảnh về một mê cung chưa được giải đáp được hiển thị bên dưới.
Và đây là giải pháp của nó.
Để giải câu đố này, trước tiên chúng ta bắt đầu với ô nguồn và di chuyển theo hướng mà đường dẫn không bị chặn. Nếu con đường đi làm cho chúng ta đến đích thì câu đố sẽ được giải quyết. Nếu không, chúng ta quay lại và thay đổi hướng của con đường đã đi. Chúng tôi cũng sẽ triển khai cùng một logic trong mã của chúng tôi.
Input:
maze[][] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}}
Output:
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1 Giải thích
Đầu tiên, chúng ta sẽ tạo một ma trận để đại diện cho mê cung và các phần tử của ma trận sẽ là 0 hoặc 1. 1 sẽ đại diện cho ô bị chặn và 0 sẽ đại diện cho các ô mà chúng ta có thể di chuyển. Ma trận cho mê cung được hiển thị ở trên là:
0 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0
Bây giờ, chúng ta sẽ tạo thêm một ma trận có cùng thứ nguyên để lưu trữ lời giải. Các phần tử của nó cũng sẽ là 0 hoặc 1. 1 sẽ đại diện cho các ô trong đường dẫn của chúng ta và phần còn lại của các ô sẽ là 0. Ma trận đại diện cho lời giải là:
1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1
Vì vậy, bây giờ chúng ta có ma trận của chúng ta. Tiếp theo, chúng tôi sẽ tìm một đường dẫn từ ô nguồn đến ô đích và các bước chúng tôi sẽ thực hiện là:
-
Kiểm tra ô hiện tại, nếu đó là ô đích thì câu đố đã được giải.
-
Nếu không, chúng tôi sẽ cố gắng di chuyển xuống dưới và xem liệu chúng tôi có thể di chuyển trong ô xuống dưới hay không (để di chuyển trong ô, ô đó phải bị bỏ trống và chưa có trong đường dẫn).
-
Nếu chúng ta có thể di chuyển đến đó, thì chúng ta sẽ tiếp tục với đường dẫn đến ô tiếp theo đi xuống.
-
Nếu không, chúng tôi sẽ cố gắng di chuyển sang ô bên phải. Và nếu nó bị chặn hoặc bị lấy đi, chúng tôi sẽ di chuyển lên trên.
-
Tương tự, nếu chúng ta cũng không thể di chuyển lên trên, chúng ta sẽ chỉ cần di chuyển sang ô bên trái.
-
Nếu không thể di chuyển trong bốn bước (xuống, phải, lên hoặc trái), chúng tôi sẽ chỉ cần quay lại và thay đổi đường dẫn hiện tại của mình (quay lui).
Vì vậy, tóm tắt là chúng ta cố gắng di chuyển đến ô khác (xuống, phải, lên và trái) từ ô hiện tại và nếu không có chuyển động nào được, thì chỉ cần quay lại và thay đổi hướng của đường dẫn đến ô khác.
printolution → Chức năng này chỉ in ma trận giải pháp.
Giải quyết → Đây là chức năng thực tế mà chúng tôi đang triển khai thuật toán quay lui. Đầu tiên, chúng tôi đang kiểm tra ô của chúng tôi có phải là ô đích hay không nếu (r ==SIZE-1) và (c ==SIZE-1). Nếu đó là ô đích thì câu đố của chúng ta đã được giải. Nếu không, thì chúng tôi đang kiểm tra xem đó có phải là ô hợp lệ để di chuyển hay không. Một ô hợp lệ phải nằm trong ma trận, tức là các chỉ số phải từ 0 đến SIZE-1 r> =0 &&c> =0 &&r Ví dụ
#include <iostream>
using namespace std;
#define SIZE 5
//the maze problem
int maze[SIZE][SIZE] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}
};
//matrix to store the solution
int solution[SIZE][SIZE];
//function to print the solution matrix
void printsolution() {
int i,j;
for(i=0;i<SIZE;i++) {
for(j=0;j<SIZE;j++) {
printf("%d\t",solution[i][j]);
}
printf("\n\n");
}
}
//function to solve the maze
//using backtracking
int solvemaze(int r, int c) {
//if destination is reached, maze is solved
//destination is the last cell(maze[SIZE-1][SIZE-1])
if((r==SIZE-1) && (c==SIZE-1) {
solution[r][c] = 1;
return 1;
}
//checking if we can visit in this cell or not
//the indices of the cell must be in (0,SIZE-1)
//and solution[r][c] == 0 is making sure that the cell is not already visited
//maze[r][c] == 0 is making sure that the cell is not blocked
if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0){
//if safe to visit then visit the cell
solution[r][c] = 1;
//going down
if(solvemaze(r+1, c))
return 1;
//going right
if(solvemaze(r, c+1))
return 1;
//going up
if(solvemaze(r-1, c))
return 1;
//going left
if(solvemaze(r, c-1))
return 1;
//backtracking
solution[r][c] = 0;
return 0;
}
return 0;
}
int main() {
//making all elements of the solution matrix 0
int i,j;
for(i=0; i<SIZE; i++) {
for(j=0; j<SIZE; j++) {
solution[i][j] = 0;
}
}
if (solvemaze(0,0))
printsolution();
else
printf("No solution\n");
return 0;
}