java 39ms solution bfs

• public class Solution {
int len_x, len_y, currentCount = 0, current_i = 0, current_j = 0;
int[][] matrixArr;
int[][] matrixArrCount;

``````public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
len_x = matrix.size();
len_y = matrix.get(0).size();
int i, j;
matrixArr = new int[len_x][len_y];
matrixArrCount = new int[len_x][len_y];
boolean[][] visited = new boolean[len_x][len_y];
for (i = 0; i < len_x; i++) {
for (j = 0; j < len_y; j++) {
matrixArr[i][j] = matrix.get(i).get(j);
}
}
for (i = 0; i < len_x; i++) {
for (j = 0; j < len_y; j++) {
if (matrixArr[i][j] == 1) {
if (matrixArrCount[i][j] == 1) {
continue;
}
current_i = i;
current_j = j;
matrixArrCount[i][j] = bfs(i, j, 1, visited);
}
}
}
for (i = 0; i < len_x; i++) {
List<Integer> list = new ArrayList<Integer>();
for (j = 0; j < len_y; j++) {
}
}
return res;
}

public int bfs(int vi, int vj, int k, boolean[][] visited) {
int count = 0, min = 0;
if (k == len_x + len_y - 1 || (currentCount > 0 && k > currentCount)) {
return 1;
}
if (vi > 0 && matrixArr[vi - 1][vj] == 0) {
matrixArrCount[vi][vj] = 1;
if (current_i == vi && current_j == vj) {
currentCount = count;
}
return 1;
}
if (vi + 1 < len_x && matrixArr[vi + 1][vj] == 0) {
matrixArrCount[vi][vj] = 1;
if (current_i == vi && current_j == vj) {
currentCount = count;
}
return 1;
}
if (vj > 0 && matrixArr[vi][vj - 1] == 0) {
matrixArrCount[vi][vj] = 1;
if (current_i == vi && current_j == vj) {
currentCount = count;
}
return 1;
}
if (vj + 1 < len_y && matrixArr[vi][vj + 1] == 0) {
matrixArrCount[vi][vj] = 1;
if (current_i == vi && current_j == vj) {
currentCount = count;
}
return 1;
}
if (currentCount > 0 && k > currentCount) {
return 1;
}
if (vi > 0 && matrixArr[vi - 1][vj] == 1 && !visited[vi - 1][vj]) {
visited[vi][vj] = true;
min = 1 + bfs(vi - 1, vj, k + 1, visited);
visited[vi][vj] = false;
if (count == 0) {
count = min;
} else if (count > min) {
count = min;
}
if (current_i == vi && current_j == vj) {
currentCount = count;
}

}
if (vi + 1 < len_x && matrixArr[vi + 1][vj] == 1
&& !visited[vi + 1][vj]) {
visited[vi][vj] = true;
min = 1 + bfs(vi + 1, vj, k + 1, visited);
visited[vi][vj] = false;
if (count == 0) {
count = min;
} else if (count > min) {
count = min;
}
if (current_i == vi && current_j == vj) {
currentCount = count;
}
}
if (vj > 0 && matrixArr[vi][vj - 1] == 1 && !visited[vi][vj - 1]) {
visited[vi][vj] = true;
min = 1 + bfs(vi, vj - 1, k + 1, visited);
visited[vi][vj] = false;
if (count == 0) {
count = min;
} else if (count > min) {
count = min;
}
if (current_i == vi && current_j == vj) {
currentCount = count;
}
}
if (vj + 1 < len_y && matrixArr[vi][vj + 1] == 1
&& !visited[vi][vj + 1]) {
visited[vi][vj] = true;
min = 1 + bfs(vi, vj + 1, k + 1, visited);
visited[vi][vj] = false;
if (count == 0) {
count = min;
} else if (count > min) {
count = min;
}
if (current_i == vi && current_j == vj) {
currentCount = count;
}
}
if (count == 0) {
count = len_x + len_y - 2;
}
return count;
}
``````

}

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