資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告