AcWing 173 矩阵距离 BFS
发布时间
阅读量：
阅读量
AcWing 173 矩阵距离
思路：通过bfs算法求解多源最短路径问题，其中将字符为1的点作为初始层，对应的距离值设定为0，并首先将这些点全部加入队列。随后依次处理该层中的每个点，对其上下左右四个方向的相邻点进行遍历，若这些点尚未被访问，则将其距离值设为当前层的距离值加一，并将其加入队列。与初始层相邻的点构成第二层，其距离值均为1。接着对第二层执行相同的操作，以此类推逐步扩展至后续各层。
需要特别注意的是，所给的A矩阵是一个字符型矩阵，在实际操作中需确保正确读取并进行相应的判断处理。
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef pair<int, int>PII;
int dis[N][N];
int n, m;
char g[N][N];
PII q[N];
int bfs(){
memset(dis, -1, sizeof dis);
queue<PII>q;
for(int i = 0; i < n; 全部评论 (0)
还没有任何评论哟~