Vấn đề chuột trong mê cung

Trong bài toán này, có một mê cung cho trước có kích thước N x N. Vị trí nguồn và đích lần lượt là ô trên cùng bên trái và ô dưới cùng bên phải. Một số ô hợp lệ để di chuyển và một số ô bị chặn. Nếu một con chuột bắt đầu di chuyển từ đỉnh xuất phát đến đỉnh đích, chúng ta phải tìm xem có cách nào để hoàn thành đường đi không, nếu có thể thì hãy đánh dấu đường đi chính xác cho con chuột đó.

Mê cung được đưa ra bằng cách sử dụng ma trận nhị phân, trong đó nó được đánh dấu bằng 1, nó là một đường dẫn hợp lệ, nếu không thì 0 cho một ô bị chặn.

LƯU Ý: Chuột chỉ có thể di chuyển theo hai hướng, sang phải hoặc hướng xuống.

Đầu vào và Đầu ra

 Input:Thuật toán này sẽ coi mê cung dưới dạng ma trận, trong ma trận, giá trị 1 biểu thị không gian trống và giá trị 0 biểu thị tường hoặc vùng bị chặn.  Trong sơ đồ này, vòng tròn trên cùng bên trái biểu thị điểm bắt đầu và vòng tròn dưới cùng bên phải biểu thị điểm kết thúc .Output:Nó sẽ hiển thị một ma trận. Từ ma trận đó, chúng ta có thể tìm ra đường đi của chuột để đến điểm đích.  

Thuật toán

isValid (x, y)

Đầu vào: x và y chỉ trong mê cung.

Đầu ra: Đúng nếu vị trí (x, y) hợp lệ, ngược lại là sai.

 Bắt đầu nếu x và y nằm trong phạm vi và (x, y) vị trí không bị chặn, sau đó trả về true trả về falseEnd 

Giải quyếtRatMaze (x, y)

Đầu vào - Điểm bắt đầu x và y.

Đầu ra - Con đường theo dõi của con chuột để đến đích, nếu không thì sai.

 Bắt đầu nếu (x, y) là góc dưới cùng bên phải, sau đó đánh dấu vị trí là 1 trả về true nếu isValidPlace (x, y) =true, sau đó đánh dấu (x, y) là 1 nếu giải quyếtRatMaze (x + 1 , y) =true, sau đó // đối với chuyển động về phía trước trả về true nếu giải quyết (x, y + 1) =true, sau đó // đối với chuyển động xuống trả về dấu true (x, y) là 0 khi chuyển động lùi trả về false trả về falseEnd  
 Ví dụ 
 
 #include  #define N 5using namespace std; int maze [N] [N] ={{1, 0, 0, 0, 0}, {1, 1, 0, 1, 0}, { 0, 1, 1, 1, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 1, 1}}; int sol [N] [N]; // nghiệm cuối cùng của đường dẫn mê cung được lưu trữ ở đâyvoid showPath () {for (int i =0; i  =0 &&x  =0 &&y  
 Đầu ra 
 
 1 0 0 0 01 1 0 0 00 1 1 1 00 0 0 1 00 0 0 1 1