หนูในปัญหาเขาวงกต

ในปัญหานี้ มีเขาวงกตขนาด N x N ที่ระบุ ตำแหน่งต้นทางและปลายทางคือเซลล์ซ้ายบนและเซลล์ขวาล่างตามลำดับ บางเซลล์สามารถย้ายได้และบางเซลล์ถูกบล็อก หากหนูตัวหนึ่งเริ่มเคลื่อนที่จากจุดยอดเริ่มต้นไปยังจุดยอดปลายทาง เราต้องพบว่ามีวิธีใดที่จะทำให้เส้นทางสมบูรณ์ หากเป็นไปได้ ให้ทำเครื่องหมายเส้นทางที่ถูกต้องสำหรับหนู

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

หมายเหตุ: หนูสามารถเคลื่อนที่ได้สองทิศทางเท่านั้น ทางขวาหรือทางลง

อินพุตและเอาต์พุต

Input:อัลกอริธึมนี้จะใช้เขาวงกตเป็นเมทริกซ์ ในเมทริกซ์ ค่า 1 จะระบุพื้นที่ว่างและ 0 หมายถึงผนังหรือพื้นที่ที่ถูกบล็อก ในแผนภาพนี้ วงกลมบนซ้ายระบุจุดเริ่มต้น และวงกลมล่างขวาระบุจุดสิ้นสุด .Output:จะแสดงเมทริกซ์ จากเมทริกซ์นั้น เราสามารถหาเส้นทางของหนูเพื่อไปยังจุดปลายทางได้ 

อัลกอริทึม

isValid(x, y)

ป้อนข้อมูล: x และ y ชี้ไปที่เขาวงกต

ผลลัพธ์: จริงถ้าตำแหน่ง (x,y) ถูกต้อง มิฉะนั้นจะเป็นเท็จ

เริ่มต้นหาก x และ y อยู่ในช่วงและ (x,y) place ไม่ถูกบล็อก จากนั้นคืนค่า true return falseEnd

solveRatMaze(x, y)

ป้อนข้อมูล − จุดเริ่มต้น x และ y

ผลผลิต − เส้นทางที่หนูไล่ไปถึงปลายทาง มิฉะนั้น จะเป็นเท็จ

เริ่มต้นหาก (x,y) เป็นมุมขวาล่าง จากนั้นทำเครื่องหมายสถานที่เป็น 1 คืนค่าเป็น true หาก isValidPlace(x, y) =true จากนั้นทำเครื่องหมาย (x, y) ให้เป็น 1 หาก SolvRatMaze(x+1 , y) =true จากนั้น //สำหรับการเคลื่อนที่ไปข้างหน้าให้คืนค่า true ถ้า dissolveRatMaze(x, y+1) =true จากนั้น //สำหรับการเคลื่อนไหวลงจะส่งกลับเครื่องหมายจริง (x,y) เป็น 0 เมื่อ backtracks คืนค่า falseEnd ที่ผิดพลาด 
ตัวอย่าง
 
#include#define N 5using เนมสเปซ 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 โซล[N][N]; // วิธีแก้ปัญหาสุดท้ายของเส้นทางเขาวงกตถูกเก็บไว้ที่นี่เป็นโมฆะ showPath() { สำหรับ (int i =0; i =0 &&x =0 &&y  
ผลลัพธ์
 
1 0 0 0 01 1 0 0 00 1 1 1 00 0 0 1 00 0 0 1 1