BFS Java Solution


  • 0
    M
        private class Pos{
            int i, j;
            public Pos(int x, int y) {
                i = x;
                j = y;
            }
        }
        public int shortestDistance(int[][] grid) {
            if (grid == null || grid.length == 0) return -1;
            int m = grid.length, n = grid[0].length;
            int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
            int num0 = 0, num1 = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == 1) ++num1;
                }
            }
            int min = Integer.MAX_VALUE;
            boolean found = false;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == 0) {
                        int sum = bfs(grid, i, j, new boolean[m][n], dx, dy, num1);
                        if (sum > 0) {
                            found = true;
                            min = Math.min(min, sum);
                        }
                    }
                }
            }
            return found ? min : -1;
        }
        private int bfs(int[][] grid, int i, int j, boolean[][] seen, int[] dx, int[] dy, int num1) {
            int cnt = 0, sum = 0;
            seen[i][j] = true;
            Queue<Pos> q = new LinkedList<>();
            q.offer(new Pos(i, j));
            int dis = 0;
            while (!q.isEmpty()) {
                int size = q.size();
                ++dis;
                for (int k = 0; k < size; ++k) {
                    Pos pos = q.poll();
                    for (int di = 0; di < dx.length; ++di) {
                        int x = pos.i + dx[di], y = pos.j + dy[di];
                        if (x >= 0 && x < grid.length && y >= 0 && y < grid[x].length && !seen[x][y]) {
                            if (grid[x][y] == 1) {
                                sum += dis;
                                ++cnt;
                            }
                            else if (grid[x][y] == 0) q.offer(new Pos(x, y));
                            seen[x][y] = true;
                        }
                    }
                }
            }
            if (cnt != num1) return -1;
            return sum;
        }
    

Log in to reply
 

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