leetcode 542 01 Matrix 详细解答
leetcode 542 01 Matrix 详细解答
解答1
这个题是找出1到最近的 0 的距离。所以应该是从某一个单元格的上下左右来分析。看1的上下左右离 0 最近的距离是多少？所以很快就能想到BFS。
这里就是先将matrix中数值为0的下标存储在队列和一个集合中。每一次取出队列头的下标（i， j），将（i，j）四个方向的下标对应的matrix加1
这里说的可能不太详细，下面是我的插图加以解释：
代码如下：
解答2
这里可以用动态规划想到一个比较巧妙的办法，因为要找出单元格的上下左右来比较最小。我们可以先找出单元格的左上，然后再找出单元格的右下离0的最近距离。
第一种情况，就是从左上往右下顺序遍历。这里的状态转移方程就是
F(x, y)= min( F(x-1, y)+1, F(x, y-1)+1) if maxtrix[x][y] != 0
第二种情况，就是从右下往左上逆序遍历。这里的状态转移方程就是
F(x, y)= min( F(x+1, y)+1, F(x, y+1)+1) if maxtrix[x][y] != 0
最后代码如下：
时间复杂度：O(MN)，空间复杂度：O(MN)