Build Post Office II

Given a 2D grid, each cell is either a wall2, an house1or empty0(the number zero, one, two), find a place to build a post office so that the sum of the distance from the post office to all the houses is smallest. Return the smallest sum of distance. Return-1if it is not possible

Example:

Given a grid:

0 1 0 0 0
1 0 0 2 1
0 1 0 0 0
return 8, You can build at (1,1).

(Placing a post office at (1,1), the distance that post office to all the house sum is smallest.)

Solution:

Use bfs to sum up all distances from each house to each empty space as follows

sumDistanceToEachEmpty = 
2 0 10 12 14 
0 8 10 0 0 
2 0 10 12 14
timeVisitedForEachEmpty =
2 0 4 4 4 
0 4 4 0 0 
2 0 4 4 4

Then, select the minimum distance where all houses have to pass by.

Code:

public class Solution {

    class Loc {
        int x;
        int y;
        public Loc(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static final int WALL = 2;
    private static final int HOUSE = 1;
    private static final int EMPTY = 0;
    private static final int[] XMOVES = {1, -1, 0, 0};
    private static final int[] YMOVES = {0, 0, 1, -1};

    private int n;
    private int m;
    private int[][] grid;
    private List<Loc> houses;
    private List<Loc> empties;
    private int[][] sumDistanceToEachEmpty = new int[n][m];
    private int[][] timeVisitedForEachEmpty = new int[n][m];

    private void initial(int[][] grid) {
        this.n = grid.length;
        this.m = grid[0].length;
        this.grid = grid;
        this.sumDistanceToEachEmpty = new int[n][m];
        this.timeVisitedForEachEmpty = new int[n][m];
        this.houses = new ArrayList<>();
        this.empties = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == HOUSE) {
                    houses.add(new  Loc(i, j));
                } else if (grid[i][j] == EMPTY) {
                    empties.add(new Loc(i, j));
                }
            }
        }
    }

    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        initial(grid);

        for (Loc house : houses) {
            bfsFindSumDistanceToEachEmpty(house);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(timeVisitedForEachEmpty[i][j] + " ");
            }
            System.out.println("");
        }
        int shortestDistance = Integer.MAX_VALUE;
        for (Loc empty : empties) {
            if (timeVisitedForEachEmpty[empty.x][empty.y] != houses.size()) {
                continue;
            }
            shortestDistance = Math.min(shortestDistance, 
                                    sumDistanceToEachEmpty[empty.x][empty.y]);
        }
        if (shortestDistance == Integer.MAX_VALUE) {
            return -1;
        }
        return shortestDistance;
    }

    private void bfsFindSumDistanceToEachEmpty(Loc house) {
        Queue<Loc> q = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        int distance = 0;
        q.offer(house);
        visited.add(house.x * m + house.y);
        while (!q.isEmpty()) {
            int size = q.size();
            distance++;
            for (int i = 0; i < size; i++) {
                Loc location = q.poll();
                for (int j = 0; j < XMOVES.length; j++) {
                    Loc temp = new Loc(
                        location.x + XMOVES[j],
                        location.y + YMOVES[j]
                    );
                    if (!locationAvaliable(temp.x, temp.y)) {
                        continue;
                    }
                    int hashIdx = temp.x * m + temp.y;
                    if (visited.contains(hashIdx)) {
                        continue;
                    }
                    q.offer(temp);
                    visited.add(hashIdx);
                    sumDistanceToEachEmpty[temp.x][temp.y] += distance;
                    timeVisitedForEachEmpty[temp.x][temp.y]++;
                }
            }
        }
    }

    private boolean locationAvaliable(int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m) {
            return false;
        }
        return grid[x][y] == EMPTY;
    }

}