数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告