# Java DFS 71ms

• 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);
}
}
}

}

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

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

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

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