Leetcode 286 Walls and Gates

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

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

Solution 1: Use BFS, store x*n+y in the queue for the node.

 public class Solution {  
   public void wallsAndGates(int[][] rooms) {  
     int m=rooms.length;  
     if (m==0) return;  
     int n=rooms[0].length;  
     Queue<Integer> q1=new LinkedList<>();  
     Queue<Integer> q2=new LinkedList<>();  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         if (rooms[i][j]==0) q1.offer(i*n+j);  
       }  
     }  
     int d=0;  
     while (!q1.isEmpty()) {  
       while (!q1.isEmpty()) {  
         int x=q1.poll();  
         int i=x/n, j=x%n;  
         helper(rooms,i+1,j,m,n,d,q2);  
         helper(rooms,i-1,j,m,n,d,q2);  
         helper(rooms,i,j+1,m,n,d,q2);  
         helper(rooms,i,j-1,m,n,d,q2);  
       }  
       Queue<Integer> temp=q1;  
       q1=q2;  
       q2=temp;  
       d++;  
     }  
   }  
   private void helper(int[][] rooms, int i, int j, int m, int n, int d, Queue<Integer> q2) {  
     if (i<0 || j<0 || i>=m || j>=n) return;  
     if (rooms[i][j]!=Integer.MAX_VALUE) return;  
     rooms[i][j]=d+1;  
     q2.offer(i*n+j);  
   }  
 }