这道题不看答案,没想出思路,做题还是不够,看了bfs的思路,然后手写了一遍,记录一下。
这道题从bfs的角度来看,思路很像最短路径的spfa的方法,不断进行松弛操作,动态逼近最优解,先把0的的点放在队列中,然后慢慢松弛其周围1的点,没必要每一个点都进行bfs操作,从而把时间复杂度降了下来。
代码:https://pastebin.com/zxQdVZuF
语法积累:
- vector套vector:
初始化:vector<vector<int> >o(len1,vector<int>(len2, INT_MAX));
操作:可以直接像二维数组调用。 - queue front(正) top(错)
另一种提供的方法从dp角度考虑,一个点受到周围(上下左右)4个点的影响,可以分2部,从左上到右下和从右下到左上两个过程处理,也可以从左下到右上和右上到左下处理,第一过程中保证两个方向的正确性,然后第二过程在第一过程基础上完成另外两个方向的正确性。
代码:https://pastebin.com/YwLmjbW4(从左下到右上和右上到左下)