รับเขาวงกตกริด n * n หนูของเราอยู่ที่มุมซ้ายบนของตาราง ตอนนี้หนูสามารถเลื่อนลงหรือไปข้างหน้าได้เท่านั้น และถ้าหากว่าบล็อกมีค่าไม่เป็นศูนย์ในตอนนี้ หนูรูปแบบนี้จะได้รับอนุญาตให้กระโดดหลายครั้งได้ การกระโดดสูงสุดที่หนูสามารถกระโดดจากเซลล์ปัจจุบันคือตัวเลขที่มีอยู่ในเซลล์ และตอนนี้คุณได้รับมอบหมายให้ค้นหาว่าหนูสามารถไปถึงมุมล่างขวาของตารางได้หรือไม่ −
Input : { { {1, 1, 1, 1},
{2, 0, 0, 2},
{3, 1, 0, 0},
{0, 0, 0, 1}
},
Output : { {1, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 1}
}
Input : {
{2, 1, 0, 0},
{2, 0, 0, 1},
{0, 1, 0, 1},
{0, 0, 0, 1}
}
Output: Path doesn't exist แนวทางในการหาแนวทางแก้ไข
ในแนวทางนี้ เราจะใช้การย้อนรอยเพื่อติดตามทุกเส้นทางที่หนูสามารถไปได้ในตอนนี้ หากหนูไปถึงจุดหมายปลายทางจากเส้นทางใด ๆ เราจะคืนค่า จริง สำหรับเส้นทางนั้นแล้วพิมพ์เส้นทาง มิฉะนั้น เราพิมพ์ว่าเส้นทางนั้นไม่มีอยู่จริง
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
#define N 4 // size of our grid
bool solveMaze(int maze[N][N], int x, int y, // recursive function for finding the path
int sol[N][N]){
if (x == N - 1 && y == N - 1) { // if we reached our goal we return true and mark our goal as 1
sol[x][y] = 1;
return true;
}
if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
sol[x][y] = 1; // we include this index as a path
for (int i = 1; i <= maze[x][y] && i < N; i++) { // as maze[x][y] denotes the number of jumps you can take //so we check for every jump in every direction
if (solveMaze(maze, x + i, y, sol) == true) // jumping right
return true;
if (solveMaze(maze, x, y + i, sol) == true) // jumping downward
return true;
}
sol[x][y] = 0; // if none are true then the path doesn't exist
//or the path doesn't contain current cell in it
return false;
}
return false;
}
int main(){
int maze[N][N] = { { 2, 1, 0, 0 }, { 3, 0, 0, 1 },{ 0, 1, 0, 1 },
{ 0, 0, 0, 1 } };
int sol[N][N];
memset(sol, 0, sizeof(sol));
if(solveMaze(maze, 0, 0, sol)){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++)
cout << sol[i][j] << " ";
cout << "\n";
}
}
else
cout << "Path doesn't exist\n";
return 0;
} ผลลัพธ์
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
คำอธิบายของโค้ดด้านบน
ในแนวทางข้างต้น เราจะตรวจสอบทุกเส้นทางที่มันสร้างขึ้นจากเซลล์ปัจจุบันของเรา และในขณะที่เราตรวจสอบนั้น เราจะทำเครื่องหมายเส้นทางให้เป็นหนึ่งเดียวในตอนนี้ เมื่อเส้นทางของเราถึงทางตัน เราจะตรวจสอบว่าทางตันนั้นเป็นจุดหมายของเราหรือไม่ ตอนนี้ ถ้านั่นไม่ใช่จุดหมายของเรา เราก็ย้อนรอย และเมื่อเราย้อนรอย เราทำเครื่องหมายเซลล์เป็น 0 เนื่องจากเส้นทางนี้ไม่ถูกต้อง และนี่คือวิธีที่โค้ดของเราดำเนินการ
บทสรุป
ในบทช่วยสอนนี้ เราจะแก้ปัญหาหนูในเขาวงกตด้วยหลายขั้นตอนหรืออนุญาตให้กระโดดได้ นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
