โปรแกรม C สำหรับหนูในเขาวงกต - Backtracking

หนูในเขาวงกตเป็นปัญหายอดนิยมที่ใช้ backtracking

เขาวงกตเป็นเมทริกซ์ 2D ที่บางเซลล์ถูกบล็อก เซลล์หนึ่งคือเซลล์ต้นทาง เริ่มจากนั้น เซลล์อีกอันคือปลายทาง ต้องหาเส้นทางจากต้นทางไปปลายทางโดยไม่เข้าเซลล์ที่ถูกบล็อก ภาพเขาวงกตที่ยังไม่แก้ด้านล่าง:

และนี่คือคำตอบ:

เพื่อแก้ปริศนานี้ เริ่มจากเซลล์ต้นทางและเคลื่อนที่ไปทิศทางที่ทางไม่ถูกบล็อก ถ้าเส้นทางนำไปสู่ปลายทาง ปริศนาแก้แล้ว มิฉะนั้นกลับมาและเปลี่ยนทิศทาง เราจะนำตรรกะนี้ไปใช้ในโค้ด

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

ขั้นตอนหาเส้นทาง:

• ตรวจสอบเซลล์ปัจจุบัน ถ้าเป็นปลายทาง ปริศนาแก้แล้ว
• ถ้าไม่ใช่ ลองเคลื่อนลง ลองขวา ลองบน ลองซ้ายตามลำดับ
• ถ้าไม่มีการเคลื่อนไหวได้ 4 ทิศทาง กลับไปเปลี่ยนเส้นทาง (backtracking)

printsolution -> พิมพ์เมทริกซ์คำตอบ

solvemaze -> ฟังก์ชันจริงที่ใช้ backtracking ตรวจสอบก่อนว่าเป็นปลายทางหรือไม่ ถ้าไม่ใช่ ตรวจสอบว่าเซลล์ถูกต้องหรือไม่ (อยู่ในเมทริกซ์ ไม่ถูกบล็อก ไม่เคยเดิน) ถ้าถูกต้อง ทำเครื่องหมายและลอง 4 ทิศทาง ถ้าทุกทิศทางล้มเหลว ยกเลิกเครื่องหมายและกลับ

ตัวอย่างโค้ด C++

#include 
using namespace std;
#define SIZE 5 // ปัญหาเขาวงกต
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}
};
// เมทริกซ์เก็บคำตอบ
int solution[SIZE][SIZE];
// ฟังก์ชันพิมพ์เมทริกซ์คำตอบ
void printsolution() {
    int i,j;
    for(i=0;i=0 && c>=0 && r