กำหนดเขาวงกต (Maze) ที่แสดงเป็นเมทริกซ์ row X col ซึ่งอุปสรรคแสดงเป็น -1 และเซลล์ว่างมีค่าอื่นนอกจาก -1 เป้าหมายคือเริ่มจากเซลล์แรก arr[0][0] และไปถึงเซลล์สุดท้าย arr[row][col] โดยที่อนุญาตให้เคลื่อนที่ได้เพียงสองทิศทาง:
- ขวา: arr[i][j] ไป arr[i][j+1] และ
- ล่าง: arr[i][j] ไป arr[i+1][j]
ทำความเข้าใจด้วยตัวอย่าง
Input - arr[row][col] = {{0, 0, 0}, {-1, -1, 0}, {0, 0, 0}}
Output - จำนวนวิธีไปถึงจุดหมายในเขาวงกตคือ: 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)
Input - arr[row][col] = {{0, 0, 0, 0}, {-1, 0, -1, 0}, {-1, 0, -1, 0}, {0, 0, 0, 0}}
Output - จำนวนวิธีไปถึงจุดหมายในเขาวงกตคือ: 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)
แนวทางที่ใช้ในโปรแกรมด้านล่าง
ในแนวทางนี้ เราจะตั้งค่า 0 ทั้งหมดเป็น 1 ก่อน เดินทางผ่านเมทริกซ์เขาวงกตอีกครั้ง และตอนนี้สำหรับแต่ละเซลล์ ถ้าเป็นอุปสรรค (-1) ให้ข้ามไป ถ้าไม่ใช่ ให้ตรวจสอบเซลล์ด้านบน (i-1, j) และเซลล์ซ้าย (i, j-1) ถ้ามันมากกว่าศูนย์ ให้บวกค่าของมันเข้าไปในเซลล์ปัจจุบัน (i, j) ด้วยวิธีนี้ เราจะได้ผลรวมที่เซลล์ (row-1, col-1) เป็นจำนวนวิธีทั้งหมดที่ไปถึงได้
- รับอาร์เรย์อินพุท arr[row][col] เป็นเขาวงกต
- ฟังก์ชัน destination_maze(int arr[row][col]) รับ arr และคืนค่าจำนวนวิธีไปถึงจุดหมายในเขาวงกต
- ถ้าเซลล์แรกถูกบล็อก คืนค่า 0 เป็นวิธีไปถึงปลายทาง
- ตอนนี้เดินทางผ่านคอลัมน์ซ้ายสุดและตั้งค่า 0 ทั้งหมดเป็น 1 ที่อุปสรรคแรกจะ break ลูปเพราะเซลล์ด้านล่างไม่สามารถไปถึงได้ เริ่มจาก i = 0 ถึง i < row ตั้ง arr[i][0] = 1 ถ้าเป็น 0
- ทำแบบเดียวกันสำหรับแถวแรกจาก j = 0 ถึง j < col ตั้ง arr[0][j] = 1 ถ้าเป็น 0
- เดินทางผ่าน 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
ตัวอย่าง
#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
