資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的矩陣廣度優先搜尋
在給定的矩陣中，有四個物件用於分析元素位置：左、右、下和上。
廣度優先搜尋就是找到給定二維矩陣中兩個元素之間的最短距離。因此，在每個單元格中，我們可以執行四個操作，可以用四個數字表示，例如：
- '2' 表示矩陣中的單元格是源。
- '3' 表示矩陣中的單元格是目標。
- '1' 表示可以沿某個方向進一步移動該單元格。
- '0' 表示矩陣中的單元格無法沿任何方向移動。
基於上述說明，我們可以在給定的矩陣上執行廣度優先搜尋操作。
解決此問題的方法
使用 BFS 遍歷整個矩陣並找到任何單元格之間最小或最短距離的演算法如下：
- 首先輸入行數和列數。
- 使用給定的行數和列數初始化矩陣。
- 一個整數函式 shortestDist(int row, int col, int mat[][col]) 以行、列和矩陣作為輸入，並返回矩陣元素之間的最短距離。
- 初始化變數 source 和 destination 以找出源元素和目標元素。
- 如果元素為 '3'，則將其標記為目標，如果元素為 '2'，則將其標記為源元素。
- 現在初始化佇列資料結構，以便在給定矩陣上實現廣度優先搜尋。
- 將矩陣的行和列作為對插入佇列。現在移動到單元格中，並確定它是否是目標單元格。如果目標單元格的距離最小或小於當前單元格，則更新距離。
- 再次移動到另一個方向，以找出單元格與當前單元格的最小距離。
- 返回最小距離作為輸出。
示例
#include<bits/stdc++.h>
using namespace std;
int findDistance(int row, int col, int mat[][5]) {
int source_i, source_j, destination_i, destination_j;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mat[i][j] == 2) {
source_i = i;
source_j = j;
}
if (mat[i][j] == 3) {
destination_i = i;
destination_j = j;
}
}
}
int dist[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++)
dist[i][j] = INT_MAX;
}
// initialise queue to start BFS on matrix
queue < pair < int, int >> q;
q.push(make_pair(source_i, source_j));
dist[source_i][source_j] = 0;
// modified BFS by add constraint checks
while (!q.empty()) {
// storing the x co-ordinate or row information of cell
int x = q.front().first;
// storing the y co-ordinate or column information of cell
int y = q.front().second;
// Remove the cell from queue
q.pop();
// If move towards left is allowed or it is the destnation cell
if (y - 1 >= 0 && (mat[x][y - 1] == 1 || mat[x][y - 1] == 3)) {
// if distance to reach the cell to the left is less than the computed previous path distance, update it
if (dist[x][y] + 1 < dist[x][y - 1]) {
dist[x][y - 1] = dist[x][y] + 1;
q.push(mkp(x, y - 1));
}
}
// If move towards right is allowed or it is the destination cell
if (y + 1 < col && (mat[x][y + 1] == 1 || mat[x][y + 1] == 3)) {
// if distance to reach the cell to the right is less than the computed previous path distance, update it
if (dist[x][y] + 1 < dist[x][y + 1]) {
dist[x][y + 1] = dist[x][y] + 1;
q.push(mkp(x, y + 1));
}
}
// If upward direction is allowed
if (x - 1 >= 0 && (mat[x - 1][y] == 1 || mat[x - 1][y] == 3)) {
if (dist[x][y] + 1 < dist[x - 1][y]) {
dist[x - 1][y] = dist[x][y] + 1;
q.push(mkp(x - 1, y));
}
}
// If downward direction allowed
if (x + 1 < row && (mat[x + 1][y] == 1 || mat[x + 1][y] == 3)) {
// if distance to reach the cell to the down is less than the computed previous path distance, update it
if (dist[x][y] + 1 < dist[x + 1][y]) {
dist[x + 1][y] = dist[x][y] + 1;
q.push(mkp(x + 1, y));
}
}
}
return dist[destination_i][destination_j];
}
int main() {
// initialising number of rows and columns
int row = 5;
int col = 5;
// initialising matrix
int mat[][5] = {
{1, 0, 0, 2, 1},
{1, 0, 1, 1, 1},
{0, 1, 1, 2, 0},
{3, 1, 0, 0, 1},
{1, 1, 0, 0, 1}
};
int answer = findDistance(row, col, mat);
// When source and destination are unreachable
if (answer == INT_MAX)
cout << "No Path Found" << endl;
else {
cout << "The Shortest Distance between Source and Destination is:" << endl;
cout << answer << endl;
}
return 0;
}輸出
The Shortest Distance between Source and Destination is:4
更新於: 2021 年 2 月 23 日
1K+ 次瀏覽
廣告