542. 01 Matrix

这道题不看答案,没想出思路,做题还是不够,看了bfs的思路,然后手写了一遍,记录一下。
这道题从bfs的角度来看,思路很像最短路径的spfa的方法,不断进行松弛操作,动态逼近最优解,先把0的的点放在队列中,然后慢慢松弛其周围1的点,没必要每一个点都进行bfs操作,从而把时间复杂度降了下来。
代码:https://pastebin.com/zxQdVZuF
语法积累:

  1. vector套vector:
    初始化:vector<vector<int> >o(len1,vector<int>(len2, INT_MAX));
    操作:可以直接像二维数组调用。
  2. queue front(正) top(错)

另一种提供的方法从dp角度考虑,一个点受到周围(上下左右)4个点的影响,可以分2部,从左上到右下和从右下到左上两个过程处理,也可以从左下到右上和右上到左下处理,第一过程中保证两个方向的正确性,然后第二过程在第一过程基础上完成另外两个方向的正确性。
代码:https://pastebin.com/YwLmjbW4(从左下到右上和右上到左下)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Given a matrix consists of 0 and 1, find the distance of ...
    greatseniorsde阅读 294评论 0 0
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,790评论 0 33
  • 当我们的能力还配不上我们的野心时,我们能做的事情是努力保持一颗宁静的心。没有人能选择自己的出生,能做的只有努力提升...
    琳阳阅读 266评论 0 3
  • 豆丁,爸爸在过去的5个月中,给你写了19封信,几乎每周一封,不管生活是怎样的琐碎,爸爸都在坚持,爸爸知道等你长大,...
    丁爸阅读 805评论 3 51