I new do dynamic programming and I am attempting the following problem on leetcode:

I have attempted the problem using top-down dynamic programming but cannot seem to get the right answer for all the test cases. In all most all cases, the matrix is almost optimized except for a few values. My algorithm entails finding a '1' and then doing a depth first search in all 4 directions and then taking the minimum of the values 1 and saving that to the memoization table (ans[][]).

I have tried to search for a top down approach but all most all the solutions are bottom up. Can anyone please help me understand why taking the minimum of the steps in all 4 directions using memoization doesn't not yield an optimal solution or what my solution is missing?

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] ans = new int[m][n];
        for(int i = 0; i <m; i  ){
            for(int j = 0; j <n; j  ){
                if(mat[i][j] == 0){
                    ans[i][j] = 0;
                }
                else{
                    ans[i][j] = -1;
                }
            }
        }
        for(int i = 0; i < m; i  ){
            for(int j = 0; j < n; j  ){
                if(ans[i][j] == - 1){
                    boolean[][] visited = new boolean[m][n];
                    ans[i][j] = dfs(i, j, m, n, mat, ans, visited);
                }
            }
        }
        for(int i = 0; i < m; i  ){
            for(int j = 0; j < n; j  ){
                    boolean[][] visited = new boolean[m][n];
                    ans[i][j] = Math.min(ans[i][j], dfs(i, j, m, n, mat, ans, visited));
            }
        }
        return ans;
    }
    
    public int dfs(int i, int j, int m, int n, int[][]mat, int[][] ans, boolean[][] visited){
        if(i >= m || i < 0 || j >=n || j < 0|| visited[i][j]){
            return Integer.MAX_VALUE;
        }
        if(mat[i][j] == 0){
            return 0;
        }
        if(ans[i][j] != -1){
            return ans[i][j];
        }
        visited[i][j] = true;
        int up =  dfs(i - 1, j, m, n, mat, ans, visited);
        int down = dfs(i   1, j, m, n, mat, ans, visited);
        int left = dfs( i, j - 1, m, n, mat, ans, visited);
        int right = dfs(i, j   1, m, n, mat, ans,visited);
        visited[i][j] = false;
        
        ans[i][j] = Math.min (up, Math.min(down, Math.min(left, right)))   1;
        return ans[i][j];
    }
}

CodePudding user response：

The 3 double-loops at the beginning could be reduced to one double-loop, the 3rd one seems to be completely superfluous. Dfs is not working here. E.g. you will go 4 fields up 1 left and 4 fields down and save 9 but actually that field could be reached in 1 step to the left, you just ignore it because you already have a result. Even if you would fix the problems, this is still O((nm)^2) instead of O(nm). For an O(nm) solution you can initialize the result with 0 where you have a 0, with -1 where there is no 0 next to it and 1 where you have a 1 with a 0 next to it, additionally add the position of this 1 to a list. Initialize c to 2. Go through the list and check the positions up, left, right and down, if it is a -1 in the result replace it by c and add this position to a new list. Replace the list by the new list, increment c and go through the list again and again until it is empty.