Walls and Gates

LintCode Q 663 - Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

• -1 - A wall or an obstacle.
• 0 - A gate.
• INF - Infinity means an empty room. We use the value 2^31 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
  Fill each empty room with the distance to its nearest gate. If it is impossible to reach a ROOM, that room should remain filled with INF

Example1
Input: [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]] ; Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Explanation:
the 2D grid is:
INF    -1     0    INF
INF    INF    INF    -1
INF    -1    INF    -1
0     -1    INF    INF
the answer is:
3    -1    0    1
2    2    1    -1
1    -1    2    -1
0    -1    3    4

Example2
Input: [[0,-1],[2147483647,2147483647]] ; Output: [[0,-1],[1,2]]

Solution

Solution : BFS

Code:

private static final int[] DIRS = new int[]{1, 0, -1, 0, 1};
private static final int INF = Integer.MAX_VALUE;

public void wallsAndGates(int[][] grid) {
	int R = grid.length, C= grid[0].length;
	
	Queue<int[]> que = new LinkedList<>();
	
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (grid[r][c] == 0) // find a gate
				que.offer(new int[]{r, c});
		}
	}
	
	while (!que.isEmpty()) {
		
		int size = que.size();
		while (size-- != 0) {
			
			int[] curr = que.poll();
			
			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] != INF) continue;
				
				que.offer(new int[]{nr, nc});
				grid[nr][nc] = grid[curr[0]][curr[1]] + 1;
			}
		}
	}
	
	return;
}