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