Smallest Rectangle Enclosing Black Pixels

LintCode Q 803 - Smallest Rectangle Enclosing Black Pixels

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.
• Each 1 marks a building which you cannot pass through.
• Each 2 marks an obstacle which you cannot pass through.

Example 1
Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]] ; Output: 7
Explanation:
In this example, there are three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
1 - 0 - 2 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Example 2
Input: [[1,0],[0,0]] ; Output: 1
In this example, there is one buildings at (0,0).
1 - 0
| |
0 - 0
The point (1,0) or (0,1) is an ideal empty land to build a house, as the total travel distance of 1 is minimal. So return 1.

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;
	int C = grid[0].length;
	int[][] reach = new int[R][C]; // record how many houses have reached this land;
	int[][] distance = new int[R][C]; // recode the total ditance from an empty land to all houses
	int building = 0; // number of houses
	
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			// find a house
			if (grid[r][c] == 1) {
				
				building++; // increase number of 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; // dist from curr house to land
				while (!que.isEmpty()) {
					
					int size = que.size(); // BFS layer by layer
					
					while (size-- != 0) {
						
						int[] curr = que.poll();
						distance[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 || grid[nr][nc] != 0 || visited[nr][nc]) continue;
							
							que.offer(new int[]{nr, nc});
							visited[nr][nc] = true;
						}   
					}
					level++; // update dist layer by layer
				}
			}
		}
	}
	
	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] == building && distance[r][c] < res)
				res = distance[r][c];
		}
	}
	
	if (res == Integer.MAX_VALUE)
		return -1;
	else
		return res;
}