Clean BFS java solution - 35ms


  • 1
    J
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return -1;
        }
        int[][] cost = new int[grid.length][grid[0].length];
        // Staring from each building, we do BFS and write the cost matrix
        for (int i = 0; i < grid.length; i ++) {
            for (int j = 0; j < grid[0].length; j ++) {
                if (grid[i][j] == 1) {
                    BFS(grid, cost, i, j);
                }
            }
        }
        // Go through the cost matrix to find the minValue that is > 0
        int minDistance = Integer.MAX_VALUE;
        for (int i = 0; i < cost.length; i ++) {
            for (int j = 0; j < cost[0].length; j ++) {
                if (grid[i][j] != 2 && grid[i][j] != 1 && cost[i][j] != 0) {
                        minDistance = Math.min(cost[i][j], minDistance);
                }
            }
        }
        return minDistance == Integer.MAX_VALUE? -1: minDistance;
    }
    private void BFS(int[][] grid, int[][] cost, int starti, int startj) {
        int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        Queue<List<Integer>> myQueue = new LinkedList<>();
        myQueue.offer(Arrays.asList(starti, startj));
        visited[starti][startj] = true;
        int distance = 0;
        while(!myQueue.isEmpty()) {
            int size = myQueue.size();
            for (int i = 0; i < size; i ++) {
                List<Integer> cur = myQueue.poll();
                int curX = cur.get(0);
                int curY = cur.get(1);
                // Fill in distance info to cost[][]
                cost[curX][curY] += distance;
                // Add next positions into myQueue
                for (int[] dir: directions) {
                    int nextX = curX + dir[0];
                    int nextY = curY + dir[1];
                    // If this position is within the range, 
                    // and it is not obstacle or building 
                    // and it is not visited, we cannot visited it. 
                    if (nextX < grid.length && nextX >= 0 && nextY < grid[0].length && nextY >= 0 &&
                        grid[nextX][nextY] != 2 && grid[nextX][nextY] != 1 && 
                        visited[nextX][nextY] == false) { 
                        myQueue.offer(Arrays.asList(nextX, nextY));    
                        visited[nextX][nextY] = true;
                    }
                }
            }
            distance ++;
        }
        // Mark all the unreachable position as obstacle, because they would never become a valid position.
        for (int i = 0; i < cost.length; i ++) {
            for (int j = 0; j < cost[0].length; j ++) {
                if (grid[i][j] != 1 && grid[i][j] != 2 && visited[i][j] == false) {
                    grid[i][j] = 2;
                }
            }
        }
    }
    

Log in to reply
 

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