Java BFS Solution


  • 0
    I
        public class Square {
            int i;
            int j;
            String building;
            public Square(int i, int j, String building) {
                this.i = i;
                this.j = j;
                this.building = building;
            }
            
        }
    
        public int shortestDistance(int[][] grid) {
            if (grid.length == 0 || grid[0].length == 0) return -1;
            Map[][] stores = new Map[grid.length][grid[0].length];
            Queue<Square> q = new LinkedList<>();
            int buildingCount = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        String name = i + " " + j;
                        buildingCount++;
                        q.add(new Square(i - 1, j, name));
                        q.add(new Square(i + 1, j, name));
                        q.add(new Square(i, j - 1, name));
                        q.add(new Square(i, j + 1, name));
                    }
                }
            }
            int steps = 0;
            boolean terminate = false;
            int result = Integer.MAX_VALUE;
            while (!q.isEmpty()) {
                int count = q.size();
                steps++;
                while (count-- > 0) {
                    Square sq = q.poll();
                    int i = sq.i;
                    int j = sq.j;
                    String name = sq.building;
                    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 0) continue;
                    if (stores[i][j] == null) stores[i][j] = new HashMap<>();
                    if (stores[i][j].containsKey(name)) continue;
                    stores[i][j].put(name, steps);
                    if (buildingCount == stores[i][j].size()) {
                        int res = 0;
                        for (Object n : stores[i][j].keySet()){
                            res += (Integer) stores[i][j].get(n);
                        }
                        result = Math.min(res, result);
                    }
                    q.add(new Square(i - 1, j, name));
                    q.add(new Square(i + 1, j, name));
                    q.add(new Square(i, j - 1, name));
                    q.add(new Square(i, j + 1, name));
                }
            }
            return result == Integer.MAX_VALUE ? -1 : result;
        }
    }

Log in to reply
 

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