# dfs. faster than the top bfs solution

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

}
``````

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