多源BFS-- 矩阵距离

这篇具有很好参考价值的文章主要介绍了多源BFS-- 矩阵距离。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

多源BFS-- 矩阵距离,ACM,算法

 

关于多源BFS,基本上就是单源BFS的简单升级了一下,比如在queue中队头开始时只有一个,我们通过这一个队头去推导其他的东西。而多源最短路就是队头一开始有1-n个可能的数,一个一个去BFS。

题目思路:

        这个题就直接把所有的1统计出来放进queue中,每次取出对头进行BFS即可,其中有两个问题:

1.我们BFS如何去找到他是0点,怎么通过0传递到下一个0。

2.如何保证他是最小值,会不会出现值覆盖的现象。

其实第一个问题我们可以直接用dist数组进行标记,一旦有0被靠近的1标记了,那么他自身我们就可以看作是个1,通过这个1我们再去找到下一个0。

第二个问题,不会出现覆盖,因为我们每次赋值之后dist就会变成附近1的dist值加1,dist!=-1(我们初始默认0的dist数组值为-1),我们每次都是取最近的,所以一旦到这个地方,其他的点就无法访问了,一旦访问便是最近距离。

千万别忘了判断数组是否越界,否则会导致段错误

#include<bits/stdc++.h>
using namespace std;
char g[1010][1010];
int n,m;
int dist[1010][1010];
typedef pair<int,int> PII;
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
void bfs()
{
    memset(dist,-1,sizeof(dist));
    queue<PII> q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(g[i][j]=='1')
            {
                q.push({i,j});
                dist[i][j]=0;
            }
        }
    }
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(x<1||x>n||y<1||y>m)
            continue;
            if(dist[x][y]!=-1)
            {
                continue;
            }
            else
            {
                dist[x][y]=dist[t.first][t.second]+1;
                q.push({x,y});
            }
        }
    }
}
int main()
{

	cin>>n>>m;
	for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
	bfs();
	for(int i=1;i<=n;i++)
	{
	    for(int j=1;j<=m;j++)
	    {
	        cout<<dist[i][j]<<" ";
	    }
	    cout<<endl;
	}
	return 0;
}

 文章来源地址https://www.toymoban.com/news/detail-611216.html

到了这里,关于多源BFS-- 矩阵距离的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 基于邻接矩阵的有向图的广度优先遍历(BFS)和深度优先遍历(DFS)算法

    概念: 广度优先遍历算法是图的另一种基本遍历算法,其基本思想是尽最大程度辐射能够覆盖的节点,并对其进行访问。 以迷宫为例,广度优先搜索则可以想象成一组人一起朝不同的方向走迷宫,当出现新的未走过的路的时候,可以理解成一个人有分身术,继续从不同的方

    2024年02月06日
    浏览(61)
  • 计算机视觉 | 基于二值图像数字矩阵的距离变换算法

    Hi,大家好,我是半亩花海。 本实验基于 OpenCV 实现了二值图像数字矩阵的距离变换算法。首先生成一个 480x480 的黑色背景图像(定义黑色为0,白色为1),在其中随机选择了三个白色像素点作为距离变换的原点,利用 OpenCV 中 distanceTransform 等相关函数计算并输出这些原点到其

    2024年04月11日
    浏览(40)
  • 《图》经典题题解(拓扑排序,DFS,BFS,Floyd,Dijkstra,LCA最近公共祖先,最小生成树,最短路径)(ACM)

    目录 拓扑排序 / 家谱树 p1359租用潜艇 P1938[USACO09NOV] Job Hunt S  最短路计数 797. 所有可能的路径  200.岛屿数量 DFS BFS 695.岛屿的最大面积 DFS BFS P1119 灾后重建  P1629 邮递员送信 法一:Floyd 法二:Dijkstra P3379 【模板】最近公共祖先(LCA) 最小生成树 法一:prim算法 法二:Kruskal算

    2024年04月14日
    浏览(40)
  • 对无向图进行邻接矩阵的转化,并且利用DFS(深度优先)和BFS(广度优先)算法进行遍历输出, 在邻接矩阵存储结构上,完成最小生成树的操作。

    目录 一 实验目的 二 实验内容及要求 实验内容: 实验要求: 三 实验过程及运行结果 一 算法设计思路 二 源程序代码 三、截图 四 调试情况、设计技巧及体会 1.掌握图的相关概念。 2.掌握用邻接矩阵和邻接表的方法描述图的存储结构。 3.掌握图的深度优先搜索和广度优

    2024年02月04日
    浏览(54)
  • 01 矩阵(力扣)多源广度优先搜索 JAVA

    给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 输入:mat = [[0,0,0],[0,1,0],[0,0,0]] 输出:[[0,0,0],[0,1,0],[0,0,0]] 输入:mat = [[0,0,0],[0,1,0],[1,1,1]] 输出:[[0,0,0],[0,1,0],[1,2,1]] 提示

    2024年02月15日
    浏览(37)
  • 多源最短路径算法:Floyd-Warshall算法分析

    在有向赋权图中(可以存在 带负权值的路径 ,但不能存在 总权值为负数的环路 ),Floyd-Warshall算法可以求出 任意两个顶点间 的最短路径 假设图中有 N 个顶点,顶点按照 0~N-1 进行编号 算法中使用 二维数组 Dist 来记录点与点之间的最短路径长度, Dist[i][j] 表示第i个顶点到第j个顶点

    2024年02月09日
    浏览(36)
  • Floyd_Warshall算法详解及实现(多源最短路径)

    小明要去这样的城市旅游(城市交通图如下),为了减轻经济负担,小明想知道任意两个城市之间的最短路径。 从图中,可以得到:小明打算去4个城市(节点数)旅游,而这4个城市之间有8条公路(边数)连通,公路上的数字(权重)表示这条公路的长短。 现在需要设计一

    2023年04月17日
    浏览(36)
  • 【图论C++】Floyd算法(多源最短路径长 及 完整路径)

    UpData Log👆 2023.9.29 更新进行中 Statement0🥇 一起进步 Statement1💯 有些描述可能不够标准,但能达其意 常见的有: DJ算法 、 Floyd算法 、 A*算法 、 Bellman-Ford 算法 、 SPFA算法 其中 A*算法 是 DJ算法 的plus版, SPFA算法 是 Bellman-Ford 算法 的plus版 算法名称 DJ算法 Floyd算法 SPFA算法

    2024年02月19日
    浏览(42)
  • 285个地级市空间权重矩阵(空间邻接、地理距离、经济距离、经济地理嵌套矩阵)

    285个地级市空间权重矩阵(空间邻接、地理距离、经济距离、经济地理嵌套矩阵) 1、范围:285个地级市 2、数据包括:包括空间邻接矩阵、空间地理距离矩阵、空间经济距离矩阵、空间经济地理嵌套矩阵 其中空间经济距离矩阵根据2003-2019年人均GDP得到 3、指标说明: 空间权

    2024年02月16日
    浏览(57)
  • matlab做经济地理、地理距离、经济距离空间权重矩阵

    首先讲下地理加权空间权重矩阵: 该矩阵的经济含义是通过不同点的坐标系之间的距离远近来衡量两地之间的关系重要程度,当两点之间距离较远,所占的权重越低,而距离越近,权重越高。故操作如下: 首先需要导入坐标数据: A=csvread(\\\'JWD.csv\\\',1,0); % JWD.csv是文件名,csvrea

    2023年04月12日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包