### HuTao_Oya_OyaOya's blog

By HuTao_Oya_OyaOya, history, 3 weeks ago,

Given an m x n binary matrix matrix, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

Code:

Queries:

Q1
Q2
Q3

 » 3 weeks ago, # |   0 9q3418
•  » » 3 weeks ago, # ^ |   0 wtf
 » 3 weeks ago, # | ← Rev. 2 →   0 Concise blog, but I can't help
 » 3 weeks ago, # |   +2 Too easy
 » 3 weeks ago, # |   0 class Solution { public: vector> dp; vector> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int dfs(vector>& grid, int i, int j) { if (grid[i][j] == 0) return 0; if (dp[i][j] != -1) return dp[i][j]; int minDist = INT_MAX - 100000; for (auto dir : directions) { int x = i + dir[0]; int y = j + dir[1]; if (x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size()) { minDist = min(minDist, dfs(grid, x, y) + 1); } } return dp[i][j] = minDist; } vector> updateMatrix(vector>& grid) { int n = grid.size(); int m = grid[0].size(); dp = vector>(n, vector(m, -1)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (grid[i][j] == 1) { dfs(grid, i, j); } else { dp[i][j] = 0; } } } return dp; } }; 
•  » » 3 weeks ago, # ^ |   0 That would lead to stack overflow due to infinite recursive calls.
•  » » » 3 weeks ago, # ^ |   0 Yup, it's happening. I don't understand why
•  » » » 3 weeks ago, # ^ |   0 Got it! can bfs help minimize these recursive calls?
•  » » » » 3 weeks ago, # ^ |   0 yeah bfs does work here, but I was more curious on how to implement recursive dp.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 why not just use multi-source bfs? With it, you will have only 1 bfs call
 » 3 weeks ago, # |   0 I could explain one possible solution, which uses bfs instead of dfs, which you probably meant when saying you wanted to write a recursive solutionYou could use multi-source 2D-bfs. You create queue, in which you put all zeros with 0 as a distance. Then you write regular bfs, where for every visited point you save its distance and mark it as viewed. Total complexity would be O(n * m)
 » 3 weeks ago, # |   0 In the first pass, the dp is set such that it is the minimum distance of 0 from the cell using only up and left directions. In the second pass, the dp will also consider the down and right direction for getting the zero. It is clear that if for some cell the shortest path to the nearest zero is only using up-left or down-right directions then it will give the correct answer. For up-right and down-left case, we could prove by induction that the dp will store the correct answer. Clearly if there is some cell where only up path leads to nearest zero, in this cell we can claim that it takes up-right direction path to find the nearest zero(even if the right path does not exist). Similar argument goes with down-left case. If we assume that all the visited cells have taken up-right and down-left path into consideration then the next cell that is to be visited will consider its right and down neighbour and eventually consider the down-left or up-right path. Hence by induction the dp array will store minimum of all types of paths to nearest zero.
 » 3 weeks ago, # |   0 why not just multisource bfs from all the 0s