Why doesn`t Regular DFS algorithm work here?


  • 0
    E

    I am running the DFS for every node similar to the other DFS problems, such as: Longest Increasing Path in a Matrix, Max Area of Island, Number of Distinct Islands etc. I have been pulling my hair to understand why it is not finding the minimum distance to zero here. any help is appreciated.

        int DFS(vector<vector<int>>& matrix, vector<vector<int>>& D, vector<vector<bool>>& V, int i, int j) {
            if(i < 0 || j < 0 || i >= D.size() || j >= D[0].size()) return 10000; // If invalid indices return max value
            if(V[i][j]) return D[i][j]; // Do not visit an entry more than once
            V[i][j] = true; // Vist the current entry
            if(matrix[i][j] == 0) D[i][j] = 0; // if the current matrix entry is ZERO set it to the distance entry
            else {
                int top = DFS(matrix, D, V, i-1, j);
                int bot = DFS(matrix, D, V, i+1, j);
                int lft = DFS(matrix, D, V, i, j-1);
                int rgt = DFS(matrix, D, V, i, j+1); // calculate the minDist for neighbours
                D[i][j] = min(min(top, bot), min(lft, rgt)) + 1;
            }
            return D[i][j];
        }
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            if(matrix.size() == 0 || matrix[0].size() == 0) return {};
            int m = matrix.size(), n = matrix[0].size();
            vector<vector<int>> D(m, vector<int>(n, 10000));
            vector<vector<bool>> V(m, vector<bool>(n, false)); // Keep the visited information of the entries
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    D[i][j] = DFS(matrix, D, V, i, j); // Run DFS for all
                }
            }
            return D;
        }
    };```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.