Build Post Office II

LintCode Q 573 - Build Post Office II

Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (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 -1 if it is not possible.

Example 1:
Input：[[0,1,0,0,0],[1,0,0,2,1],[0,1,0,0,0]] ; Output：8
Explanation： Placing a post office at (1,1), the distance that post office to all the house sum is smallest.

Example 2:
Input：[[0,1,0],[1,0,1],[0,1,0]] ; Output：4
Explanation： Placing a post office at (1,1), the distance that post office to all the house sum is smallest.

Challenge: Solve this problem within O(n^3) time.

Notice:

• You cannot pass through wall and house, but can pass through empty.
• You only build post office on an empty.

Solution

Solution : BFS

• Use BFS to calculte the distance from house to every empty land in the graph.
• Add distances of all houses to every empty land together.
• Choose the smallest distance

Code:

private static final int[] DIRS = new int[]{1, 0, -1, 0, 1};
	public int shortestDistance(int[][] grid) {

	int R = grid.length, C = grid[0].length;
	int[][] dist = new int[R][C];
	int[][] reach = new int[R][C];
	int house = 0;
	
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (grid[r][c] == 1) {
				house++;
				
				Queue<int[]> que = new LinkedList<>();
				que.offer(new int[] {r, c});
				
				boolean[][] visited = new boolean[R][C];
				visited[r][c] = true;
				
				int level = 0;
				while (!que.isEmpty()) {
					
					int size = que.size();
					
					while (size-- != 0) {
						
						int[] curr = que.poll();
						dist[curr[0]][curr[1]] += level;
						reach[curr[0]][curr[1]]++;
						
						for (int i = 0; i < 4; i++) {
							int nr = curr[0] + DIRS[i];
							int nc = curr[1] + DIRS[i + 1];
							
							if (nr < 0 || nc < 0 || nr == R || nc == C || visited[nr][nc] || grid[nr][nc] != 0) continue;
							
							que.offer(new int[]{nr, nc});
							visited[nr][nc] = true;
						}
					}
					
					level++;
				}
			}
		}
	}
	
	int res = Integer.MAX_VALUE;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (grid[r][c] == 0 && reach[r][c] == house && dist[r][c] < res)
				res = dist[r][c];
		}
	}
	
	return res == Integer.MAX_VALUE ? -1 : res;
}