หนูในเขาวงกตเป็นปัญหายอดนิยมอย่างหนึ่งที่ใช้การย้อนรอย ฉัน
เขาวงกตเป็นเมทริกซ์ 2 มิติซึ่งบางเซลล์ถูกบล็อก หนึ่งในเซลล์คือเซลล์ต้นทาง ซึ่งเราต้องเริ่มต้น และอีกจุดหนึ่งคือจุดหมายปลายทางที่เราต้องไปให้ถึง เราต้องหาเส้นทางจากต้นทางไปยังปลายทางโดยไม่เคลื่อนเข้าไปในเซลล์ใดๆ ที่ถูกบล็อก รูปภาพของเขาวงกตที่ยังไม่ได้แก้แสดงอยู่ด้านล่าง
และนี่คือทางออก
ในการไขปริศนานี้ ก่อนอื่นเราเริ่มต้นด้วยเซลล์ต้นทางและเคลื่อนที่ไปในทิศทางที่เส้นทางไม่ถูกบล็อก หากเส้นทางที่พาทำให้เราไปถึงที่หมายปริศนาก็จะไขได้ มิฉะนั้นเรากลับมาและเปลี่ยนทิศทางของเส้นทางที่เดิน เราจะใช้ตรรกะเดียวกันนี้ในโค้ดของเราด้วย
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 คำอธิบาย
ประการแรก เราจะสร้างเมทริกซ์เพื่อเป็นตัวแทนของเขาวงกต และองค์ประกอบของเมทริกซ์จะเป็น 0 หรือ 1 1 จะแทนเซลล์ที่ถูกบล็อก และ 0 จะแสดงเซลล์ที่เราสามารถเคลื่อนที่ได้ เมทริกซ์สำหรับเขาวงกตที่แสดงด้านบนคือ:
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
ตอนนี้ เราจะสร้างเมทริกซ์ที่มีมิติเดียวกันอีกหนึ่งรายการเพื่อเก็บโซลูชัน องค์ประกอบของมันจะเป็น 0 หรือ 1 อย่างใดอย่างหนึ่ง 1 จะแสดงเซลล์ในเส้นทางของเราและส่วนที่เหลือของเซลล์จะเป็น 0 เมทริกซ์ที่เป็นตัวแทนของโซลูชันคือ:
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
ดังนั้นตอนนี้เรามีเมทริกซ์ของเราแล้ว ต่อไป เราจะพบเส้นทางจากเซลล์ต้นทางไปยังเซลล์ปลายทาง และขั้นตอนที่จะดำเนินการคือ:
-
ตรวจสอบเซลล์ปัจจุบัน หากเป็นเซลล์ปลายทาง ปริศนาก็จะได้รับการแก้ไข
-
ถ้าไม่เช่นนั้น เราจะพยายามเลื่อนลงด้านล่างและดูว่าเราสามารถเคลื่อนที่ในเซลล์ด้านล่างได้หรือไม่ (หากต้องการย้ายในเซลล์ เซลล์จะต้องว่างและยังไม่มีอยู่ในเส้นทาง)
-
หากเราสามารถย้ายไปที่นั่นได้ เราจะดำเนินการตามเส้นทางไปยังเซลล์ด้านล่างถัดไป
-
ถ้าไม่เราจะพยายามย้ายไปยังเซลล์ทางขวา และหากถูกขวางหรือยึดเราจะก้าวขึ้นไป
-
ในทำนองเดียวกัน หากเราไม่สามารถเลื่อนขึ้นได้เช่นกัน เราจะย้ายไปยังเซลล์ด้านซ้าย
-
หากไม่มีการเคลื่อนไหวทั้งสี่ (ลง ขวา ขึ้น หรือซ้าย) เราจะย้อนกลับไปและเปลี่ยนเส้นทางปัจจุบันของเรา (ย้อนรอย)
สรุปคือเราพยายามย้ายไปยังเซลล์อื่น (ลง ขวา ขึ้น และซ้าย) จากเซลล์ปัจจุบัน และหากไม่สามารถเคลื่อนไหวได้ ให้กลับมาและเปลี่ยนทิศทางของเส้นทางไปยังเซลล์อื่น
printsolution → ฟังก์ชันนี้เป็นเพียงการพิมพ์เมทริกซ์ของโซลูชัน
Solvmaze → นี่คือฟังก์ชันจริงที่เราใช้อัลกอริธึมการย้อนรอย ประการแรก เรากำลังตรวจสอบเซลล์ของเราว่าเป็นเซลล์ปลายทางหรือไม่ ถ้า (r==SIZE-1) และ (c==SIZE-1) หากเป็นเซลล์ปลายทาง แสดงว่าปริศนาของเราได้รับการแก้ไขแล้ว ถ้าไม่เช่นนั้นเรากำลังตรวจสอบว่าเป็นเซลล์ที่ถูกต้องที่จะย้ายหรือไม่ เซลล์ที่ถูกต้องต้องอยู่ในเมทริกซ์ กล่าวคือ ดัชนีต้องอยู่ระหว่าง 0 ถึง SIZE-1 r>=0 &&c>=0 &&rตัวอย่าง
#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;
}
