矩阵中两元素最小曼哈顿距离

看到有人写了这句：

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

对于每一个1进行bfs，会产生一个距离场，场里每个点的value就是这个点到场中心1的距离。
所有的1对应的距离场叠加（累积），场值最小的2的位置就是解。

具体的话，刷题网伞妖漆

多谢楼主分享，曼哈顿这个该怎么做呢？从每个1做dfs？

感谢楼主分享，我觉得最直接的应该就是对每个1进行bfs， 然后返回距离最近的2， 然后比较得出最短的距离。
还有一种想法就是能不能同时对所有2同时进行bsf，首先遇到的1就是最短距离，这个思路和bidirectional bsf差不多，只是同时搜索。

yangyuzhiguang 发表于 2019-3-18 11:22
感谢楼主分享，我觉得最直接的应该就是对每个1进行bfs， 然后返回距离最近的2， 然后比较得出最短的距离。
...

其实就是变图中单源最短路径为多源最短路径

bdhmwzfa 发表于 2019-3-18 20:52
其实就是变图中单源最短路径为多源最短路径

给我指点迷津了
谢谢。

我觉得是把所有的1同时放进队列里，然后按层遍历，第一个遇到的2就是最短的2.

好像就是多源最短路径，直接bfs应该就可以。