数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中检查二维矩阵中的可能路径
假设我们有一个二维数组。我们必须找到是否可以从左上角到右下角获得一条路径。矩阵填充了 0 和 1。0 表示开放区域，1 表示阻塞。请注意，左上角始终为 1。
假设矩阵如下所示：
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
一条路径用绿色标记，还有一些其他路径。因此，如果存在路径，则程序将返回 true，否则返回 false。
我们将通过将所有可访问的节点更改为 -1 来解决此问题，首先将起点的值更改为 -1，然后获取第一行中的下一个值，并将其与前一个值进行比较，如果该值可达（不是 0），则将当前值设置为前一个值。对列值也执行相同的操作。通过比较并将当前值与前一列值（如果该值可达）进行设置。然后从第一行第一列开始，获取前一行的值、前一列的值，获取它们之间的最小值。并将当前索引设置为最小值。如果当前索引为 1，则没有变化。最后，如果最终索引与右下角相同，则返回 true，否则返回 false。
示例
#include <iostream>
#define row 5
#define col 5
using namespace std;
bool isPathPresent(int arr[row][col]) {
arr[0][0] = -1;
for (int i = 1; i < row; i++)
if (arr[i][0] != 1)
arr[i][0] = arr[i - 1][0];
for (int j = 1; j < col; j++)
if (arr[0][j] != 1)
arr[0][j] = arr[0][j - 1];
for (int i = 1; i < row; i++)
for (int j = 1; j < col; j++)
if (arr[i][j] != 1)
arr[i][j] = min(arr[i][j - 1], arr[i - 1][j]);
return (arr[row - 1][col - 1] == -1);
}
int main() {
int arr[row][col] = {{ 0, 0, 0, 1, 0},
{1, 0, 0, 1, 1},
{ 0, 0, 0, 1, 0},
{1, 0, 0, 0, 0},
{ 0, 0, 1, 0, 0}};
if (isPathPresent(arr))
cout << "Path is present";
else
cout << "No path has found";
}输出
Path is present
更新于： 2019 年 10 月 21 日
513 次查看
广告