กำหนดเขาวงกตที่แสดงเป็นเมทริกซ์แถว X ซึ่งสิ่งกีดขวางจะแสดงเป็น -1 และเซลล์ที่ชัดเจนมีค่าอื่นที่ไม่ใช่ -1 เป้าหมายคือการเริ่มจากเซลล์แรก arr[0][0] และไปถึงเซลล์สุดท้าย arr[row][col] เพื่อให้อนุญาตเพียงสองการเคลื่อนไหว:
- เลื่อนไปทางขวา arr[i][j] ไปยัง arr[i][j+1] และ
- ลง arr[i][j] ถึง arr[i+1][j].
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล - arr[row][col] ={{0, 0, 0}, {-1, -1, 0}, {0, 0, 0}}
ผลลัพธ์ - จำนวนวิธีไปถึงที่หมายในเขาวงกตคือ 1
คำอธิบาย
0 1 2
0 0 0 0
1 -1 -1 0
2 0 0 0
ทางจะเป็น :
- เซลล์ (0,0) → เซลล์ (0,1) → เซลล์ (0,2) → เซลล์(1,2) → เซลล์(2,0)
ป้อนข้อมูล - arr[row][col] ={ {0, 0, 0, 0}, {-1, 0, -1, 0}, {-1, 0, -1, 0}, {0, 0, 0, 0}}
ผลลัพธ์ - จำนวนวิธีไปถึงที่หมายในเขาวงกตคือ:2
คำอธิบาย
0 1 2 3
0 0 0 0 0
1 -1 0 -1 0
2 -1 0 -1 0
3 0 0 0 0
ทางจะเป็น :
- เซลล์ (0,0) → เซลล์ (0,1) → เซลล์ (1,1) → เซลล์(2,1) → เซลล์(3,1) → เซลล์(3,2) → เซลล์(3,3 )
- เซลล์ (0,0) → เซลล์ (0,1) → เซลล์ (0,2) → เซลล์(0,3) → เซลล์(1,3) → เซลล์(2,3) → เซลล์(3,3 )
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
ในวิธีนี้เราจะตั้งค่าศูนย์ทั้งหมดเป็น 1 ก่อน ข้ามเมทริกซ์เขาวงกตอีกครั้งและตอนนี้สำหรับแต่ละเซลล์ หากมีการอุดตัน (-1) ก็ไม่ต้องสนใจ หากไม่เป็นเช่นนั้น ให้ตรวจสอบเซลล์บน (i-1,j) และเซลล์ด้านซ้าย (i,j-1) หากมีค่ามากกว่าศูนย์ ให้เพิ่มค่าลงในเซลล์ปัจจุบัน (i,j) ด้วยวิธีนี้เราจะได้ผลรวมที่เซลล์ (แถว-1,col-1) เป็นวิธีการเข้าถึงทั้งหมด
- รับอาร์เรย์อินพุต arr[row][col] เป็นเขาวงกต
- ฟังก์ชัน destination_maze(int arr[row][col]) รับ arr และส่งกลับจำนวนวิธีที่จะไปถึงปลายทางในเขาวงกต
- หากเซลล์แรกถูกบล็อก ให้คืนค่า 0 เพื่อไปยังจุดสิ้นสุด
- ตอนนี้สำรวจคอลัมน์ซ้ายสุดและตั้งค่า 0s ทั้งหมดเป็น 1 ในตอนแรกการอุดตันจะทำลายลูปเนื่องจากไม่สามารถเข้าถึงเซลล์ด้านล่างได้ เริ่มจากดัชนี i=0 ถึง i
- ทำเช่นเดียวกันสำหรับแถวแรกจาก j=0 ถึง j
- สำรวจ arr อีกครั้งจากเซลล์ (1,1) และถ้า arr[i][j] เป็น -1 ก็ไม่ต้องทำอะไร
- หาก arr[i-1][j] หรือ arr[i][j-1] มากกว่า 0 แล้ว arr[i][j] จะสามารถเข้าถึงได้จากพวกเขา ดังนั้นจงเพิ่มคุณค่าของมันเข้าไป
- ในตอนท้าย เราจะมี arr[row-1][col-1] เป็นวิธีการเข้าถึงทั้งหมด
- ถ้าเป็น>0 ให้คืนค่าอื่นเป็น 0
- ทำเช่นเดียวกันสำหรับแถวแรกจาก j=0 ถึง j
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
int destination_maze(int arr[row][col]) {
if (arr[0][0] == -1) {
return 0;
}
for (int i = 0; i < row; i++) {
if (arr[i][0] == 0) {
arr[i][0] = 1;
} else {
break;
}
}
for (int i = 1; i < col; i++) {
if (arr[0][i] == 0) {
arr[0][i] = 1;
} else {
break;
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (arr[i][j] == -1) {
continue;
}
if (arr[i - 1][j] > 0) {
arr[i][j] = (arr[i][j] + arr[i - 1][j]);
}
if (arr[i][j - 1] > 0) {
arr[i][j] = (arr[i][j] + arr[i][j - 1]);
}
}
}
if (arr[row - 1][col - 1] > 0) {
return arr[row - 1][col - 1];
} else {
return 0;
}
}
int main() {
int arr[row][col] = {
{
0,
0,
0
},
{
-1,
-1,
0
},
{
0,
0,
0
}
};
cout << "Count of number of ways to reach destination in a Maze are: " << destination_maze(arr);
return 0;
} หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Count of number of ways to reach destination in a Maze are: 1
