java 39ms solution bfs


  • 0
    Y

    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++) {
    			list.add(matrixArrCount[i][j]);
    		}
    		res.add(list);
    	}
    	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;
    	}
    	// adjacent cells is not 0,visit the next adjacent cells
    	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;
    }
    

    }


Log in to reply
 

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