[多源bfs] aw173. 矩阵距离(多源bfs+模板题)
2021/6/13 10:24:37
本文主要是介绍[多源bfs] aw173. 矩阵距离(多源bfs+模板题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接:173. 矩阵距离
2. 题目解析
一般来讲,bfs
求最短路、最短距离只有一个起点,那么我们初始化就只往队列中添加这个起点,让其分层拓展即可。
但是,也可以有多个起点,且性质相同。等价来看就可以将多个起点初始全部放入队列,让其当做第一层,第 0 层可以视为一个虚拟源点,它连接到这些起点且花费为 0。 这个和图论中的概念相同。
多源 bfs
就是初始化将起点(源点)全部加入队列,并进行相应初始化,剩余操作和普通 bfs
求最短路一致。
时间复杂度: O ( n m ) O(nm) O(nm)
空间复杂度: O ( n m ) O(nm) O(nm)
好题,多观察观察数据
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 1005; int n, m; char g[N][N]; int dist[N][N]; PII q[N * N]; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; void bfs() { int hh = 0, tt = -1; memset(dist, -1, sizeof dist); for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) if (g[i][j] == '1') { q[ ++ tt ] = {i, j}; dist[i][j] = 0; } while (hh <= tt) { auto t = q[hh ++ ]; int x = t.first, y = t.second; for (int i = 0; i < 4; i ++ ) { int a = x + dx[i], b = y + dy[i]; if (a < 0 || a >= n || b < 0 || b >= m) continue; if (dist[a][b] != -1) continue; dist[a][b] = dist[x][y] + 1; q[ ++ tt ] = {a, b}; } } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) // 不要 %d,直接读入一个整数了...scanf("%1d", &g[i][j])也可... scanf("%s", g[i]); bfs(); for (int i = 0; i < n; i ++ ) { for (int j = 0; j < m; j ++ ) printf("%d ", dist[i][j]); puts(""); } return 0; }
这篇关于[多源bfs] aw173. 矩阵距离(多源bfs+模板题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)