dfs. faster than the top bfs solution


  • 0
    Y

    the idea is use 0 to turn 1 to -1
    use -1 to turn 1 to -2
    use -2 to turn 1 to -3
    ....
    until all the nodes are visited.

    Then turn all the nodes to -nodes.

        private boolean[][] mark = null;
        private int[][] mtx = null;
        private int m = 0;
        private int n = 0;
        private int cnt = 0;  // visited nodes.
    
        public int[][] updateMatrix(int[][] matrix) {
            m = matrix.length;
            if (0 == m) return matrix;
    
            n = matrix[0].length;
            if (0 == n) return matrix;
    
            mark = new boolean[m][n];
            mtx = matrix;
            
            int marker = 0;
            while (cnt != m * n) {
                for (int row = 0; row < m; ++row) {
                    for (int col = 0; col < n; ++col) {
                        if (!mark[row][col] && marker == mtx[row][col])  {
                            dfs(marker, row, col);
                        }
                    }
                }
                --marker;
            }
    
            for (int row = 0; row < m; ++row) {
                for (int col = 0; col < n; ++col) {
                    mtx[row][col] = -mtx[row][col];
                }
            }
    
            return mtx;
        }
    
        private void dfs(int marker, int row, int col) {
            mark[row][col] = true;
            ++cnt;
    
            if (row + 1 < m)  {
                if (!mark[row + 1][col] && mtx[row + 1][col] == marker) dfs(marker,row + 1, col);
                else if (1 == mtx[row + 1][col]) mtx[row + 1][col] = marker - 1;
            }
    
            if (row -1 >= 0)  {
                if (!mark[row - 1][col] && mtx[row - 1][col] == marker) dfs(marker,row - 1, col);
                else if (1 == mtx[row - 1][col]) mtx[row - 1][col] = marker - 1;
            }
    
            if (col + 1 < n)  {
                if (!mark[row][col + 1] && mtx[row][col + 1] == marker) dfs(marker,row, col + 1);
                else if (1 == mtx[row][col + 1]) mtx[row][col + 1] = marker - 1;
            }
    
            if (col - 1 >= 0)  {
                if (!mark[row][col - 1] && mtx[row][col - 1] == marker) dfs(marker,row, col - 1);
                else if (1 == mtx[row][col - 1]) mtx[row][col - 1] = marker - 1;
            }
    
        }
    

Log in to reply
 

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