在C ++中对矩阵进行广度优先搜索
在给定的矩阵中，有四个对象可以分析元素的位置：左，右，下和上。
广度优先搜索仅是找到给定的二维矩阵的两个元素之间的最短距离。因此，在每个单元格中，我们可以执行四个操作，这些操作可以用四个数字表示，例如，
“2”表示矩阵中的单元格是“源”。
“3”表示矩阵中的单元格是“目标”。
“1”表示该单元可以沿一个方向进一步移动。
“0”表示矩阵中的单元不能沿任何方向移动。
基于adobe合理性，我们可以对给定的矩阵执行广度优先搜索操作。
解决这个问题的方法
使用BFS遍历整个矩阵并找到任何像元之间的最小或最短距离的算法如下：
首先获取输入的行和列。
用给定的行和列初始化矩阵。
整数函数shortestDist（introw，intcol，intmat[][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;
}
//初始化队列以在矩阵上启动BFS
queue < pair < int, int >> q;
q.push(make_pair(source_i, source_j));
dist[source_i][source_j] = 0;
//通过添加约束检查来修改BFS
while (!q.empty()) {
//存储单元格的x坐标或行信息
int x = q.front().first;
//存储单元格的y坐标或列信息
int y = q.front().second;
//从队列中删除单元格
q.pop();
//如果允许向左移动或它是目标单元格
if (y - 1 >= 0 && (mat[x][y - 1] == 1 || mat[x][y - 1] == 3)) {
//如果到达单元格左侧的距离小于计算的先前路径距离，请对其进行更新
if (dist[x][y] + 1 < dist[x][y - 1]) {
dist[x][y - 1] = dist[x][y] + 1;
q.push(mkp(x, y - 1));
}
}
//如果允许向右移动或它是目标单元格
if (y + 1 < col && (mat[x][y + 1] == 1 || mat[x][y + 1] == 3)) {
//如果到达右侧像元的距离小于计算的先前路径距离，请对其进行更新
if (dist[x][y] + 1 < dist[x][y + 1]) {
dist[x][y + 1] = dist[x][y] + 1;
q.push(mkp(x, y + 1));
}
}
//如果允许向上方向
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 (x + 1 < row && (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));
}
}
}
return dist[destination_i][destination_j];
}
int main() {
//初始化行数和列数
int row = 5;
int col = 5;
//初始化矩阵
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);
//当源和目标不可访问时
if (answer == INT_MAX)
cout << "No Path Found" << endl;
else {
cout << "源到目的地的最短距离是：" << endl;
cout << answer << endl;
}
return 0;
}输出结果源到目的地的最短距离是：4