Java DFS 71ms


  • 0

    Without noAdjZero, the DFS solution will get TLE.
    noAdjZero check whether a 1 has adjacent 0. If yes, keep it, if not, change it to 10000 as the maximum length.

    public class Solution {
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            
            for(int row = 0; row < matrix.size(); row ++)
                for(int col = 0; col < matrix.get(0).size(); col++)
                    if(matrix.get(row).get(col) == 1 && noAdjZero(matrix, row, col))
                            matrix.get(row).set(col, 10000);
                
            for(int row = 0; row < matrix.size(); row ++)
                for(int col = 0; col < matrix.get(0).size(); col++)
                    DFS(matrix, row, col);
            
            return matrix;
        }
        
        public boolean noAdjZero(List<List<Integer>> matrix, int row, int col){
            int[][] direction = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
            
            for(int[] d : direction){
                int newRow = row + d[0], newCol = col + d[1];
                if(newRow < 0 || newRow >= matrix.size() || newCol < 0 || newCol >= matrix.get(0).size())   continue;
                
                if(matrix.get(newRow).get(newCol) == 0) return false;
            }
            return true;
        }
        
        public void DFS(List<List<Integer>> matrix, int row, int col){
            int[][] direction = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
            
            for(int[] d : direction){
                int newRow = row + d[0], newCol = col + d[1];
                if(newRow < 0 || newRow >= matrix.size() || newCol < 0 || newCol >= matrix.get(0).size())   continue;
                
                if(matrix.get(newRow).get(newCol) > matrix.get(row).get(col) + 1){
                    matrix.get(newRow).set(newCol,matrix.get(row).get(col) + 1);
                    DFS(matrix, newRow, newCol);
                }
            }
        }
        
    }
    

  • 1

    I guess I should've used "thicker stripes". For example for [[1] * 3333, [1] * 3333, [0] * 3333] you take about 500ms.


  • 0

    @StefanPochmann You are right. DFS is indeed not a good idea for this problem.


  • 0

    @fallcreek
    I agree with you, DFS works not good in this problem.


Log in to reply
 

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