HuTao_Oya_OyaOya's blog

How does this kind of DP even work ?
By HuTao_Oya_OyaOya, history, 4 months ago, In English

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

Thanks for your time.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

9q3418

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Concise blog, but I can't help

→ Reply
»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Too easy

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
class Solution {
public:
    vector<vector<int>> dp;
    vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    int dfs(vector<vector<int>>& 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<vector<int>> updateMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        dp = vector<vector<int>>(n, vector<int>(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;
    }
};
→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I could explain one possible solution, which uses bfs instead of dfs, which you probably meant when saying you wanted to write a recursive solution

You 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)

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why not just multisource bfs from all the 0s

→ Reply