My Easy understanding Java BFS version, with comments


  • 3
    public class Solution {
        public int shortestDistance(int[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            //find the number of buildings
            int num = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        num++;
                    }
                }
            }
            //build the distance of each builder
            int[][][] res = new int[num][grid.length][grid[0].length];
            num = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        build(res,grid,i,j,num,1);
                        num++;
                    }
                }
            }
            //find min
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {    
                    if (grid[i][j] == 0) {
                        int temp = findRoute(res,i,j);
                        min = Math.min(min,temp);
                    }
                }
            }
            if (min == Integer.MAX_VALUE) {
                return -1;
            } else {
                return min;
            }
        }
        private int findRoute(int[][][] res, int i, int j) {
            int num = 0;
            for (int k = 0; k < res.length; k++) {
                if (res[k][i][j] == 0) {
                    return Integer.MAX_VALUE;
                } else {
                    num += res[k][i][j];
                }
            }
            return num;
        }
        private void build (int[][][] res, int[][] grid, int i, int j,int num, int dis) {
            //bfs
            Queue<Position> queue = new LinkedList<Position>();
            boolean[][] visited = new boolean[grid.length][grid[0].length];
            Position p = new Position(i,j,1);
            visited[i][j] = true;
            queue.offer(p);
            while (!queue.isEmpty()) {
                Position temp = queue.poll();
                i = temp.x;
                j = temp.y;
                dis = temp.dis;
                if (i-1 >= 0 && grid[i-1][j] == 0 && visited[i-1][j] == false) {
                    res[num][i-1][j] = dis;
                    temp = new Position(i-1,j,dis+1);
                    queue.offer(temp);
                    visited[i-1][j] = true;
                }
                if (i+1 < grid.length && grid[i+1][j] == 0 && visited[i+1][j] == false) {
                    res[num][i+1][j] = dis;
                    temp = new Position(i+1,j,dis+1);
                    queue.offer(temp);
                    visited[i+1][j] = true;
                }
                if (j-1 >= 0 && grid[i][j-1] == 0 && visited[i][j-1] == false) {
                    res[num][i][j-1] = dis;
                    temp = new Position(i,j-1,dis+1);
                    queue.offer(temp);
                    visited[i][j-1] = true;
                }
                if (j+1 < grid[0].length && grid[i][j+1] == 0 && visited[i][j+1] == false) {
                    res[num][i][j+1] = dis;
                    temp = new Position(i,j+1,dis+1);
                    queue.offer(temp);
                    visited[i][j+1] = true;
                }
            }
        }
        class Position {
            int x;
            int y;
            int dis;
            public Position(int x, int y, int dis) {
                this.x = x;
                this.y = y;
                this.dis = dis;
            }
        }
    }

  • 0
    C

    This version is Too long... but the thinking process is straightforward....


Log in to reply
 

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