資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 統計迷宮中到達目的地的路徑數
給定一個表示為行 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）。這樣，我們將得到單元格 (row-1,col-1) 處的總和作為到達它的總路徑數。
- 將輸入陣列 arr[row][col] 作為迷宮。
- 函式 destination_maze(int arr[row][col]) 獲取 arr 並返回迷宮中到達目的地的路徑數。
- 如果第一個單元格被阻塞，則返回 0 作為到達終點的路徑數。
- 現在遍歷最左邊的列並將所有 0 設定為 1。首先，障礙物會中斷迴圈，因為其下面的單元格無法到達。從索引 i=0 到 i<row 開始，如果 arr[i][0] 為 0，則將其設定為 1。
- 同樣，對第一行從 j=0 到 j<col 執行相同的操作，如果 arr[j][0] 為 0，則將其設定為 1。
- 再次遍歷 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
更新於： 2021年1月29日
446 次瀏覽
廣告