หนูในเขาวงกตเป็นปัญหายอดนิยมอย่างหนึ่งที่ใช้การย้อนรอย ฉัน
เขาวงกตเป็นเมทริกซ์ 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; }