day1.矩阵距离
2022/5/11 23:17:27
本文主要是介绍day1.矩阵距离,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
BFS证明
多源BFS
求矩阵中每个0
到最近的1
的距离(有很多源点,求到其他点的到每个源点的最短距离)
矩阵距离
1.按距离扩展:距离为0的点、为1、为2、为3...的点。
2.建立虚拟源点,求虚拟源点到其他点的最短距离(Dijkstra)
上图Dijkstra求从虚拟源点到其他点的最短距离,等价于BFS把所有
起点
放到队列中,进行扩展。
CODE
#include<iostream> #include<cstring> using namespace std; typedef pair<int,int> PII; const int N = 1010; #define x first #define y second char g[N][N]; int n,m; int d[N][N]; PII q[N * N]; void bfs() { memset(d,-1,sizeof d); int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1}; int hh = 0,tt = -1; for(int i = 0;i < n;i++) for(int j = 0;j < m;j++) if(g[i][j] == '1') { q[++tt] = {i,j}; d[i][j] = 0; } while(hh <= tt) { PII t = q[hh++]; for(int i = 0;i < 4;i++) { int a = t.x + dx[i],b = t.y + dy[i]; if(a < 0 || a >= n || b < 0 || b >= m) continue; if(d[a][b] != -1) continue; d[a][b] = d[t.x][t.y] + 1; q[++tt] = {a,b}; } } } int main() { cin>>n>>m; for(int i = 0;i < n;i++) cin>>g[i]; bfs(); for(int i = 0;i < n;i++) { for(int j = 0;j < m;j++) cout<<d[i][j]<<' '; puts(""); } return 0; }
这篇关于day1.矩阵距离的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了