20ms Clear Java BFS solution with Brief Explanation


  • 0

    The idea is for each encountered ZERO cell, do a BFS to the around empty cells. And update any empty cell's distance if smaller. Note that below code I did 2 major code refactoring to make it more concise:

    1. I only add cell into queue if its cell's value needs to be
      updated, alternatively, you can update in the next outer queue loop,
      but queue offer and poll operations take some overheads.

    2. I did not maintain a visited states (which is quite common in
      BFS), because for visited cells, the cell's value must have been
      updated to previous smaller COUNT, while the COUNT will increase
      with BFS level.

    3. Such a simple check rooms[i-1][j]>count+1 will skip -1, 0 and those visited cells!

      public class Solution {
      
          public void bfs(int[][] rooms, int i, int j) {
              int r = rooms.length;
              int c = rooms[0].length;
              Queue<Integer> q = new LinkedList<>();
              q.offer(i*c+j);
              int count = -1;
              while(!q.isEmpty()) {
                  count++;
                  int size = q.size();
                  while(size-->0) {
                      i = q.peek() / c;
                      j = q.peek() % c;
                      q.poll();
                      rooms[i][j] = count;
                      if(i>0 && rooms[i-1][j]>count+1)
                          q.offer((i-1)*c+j);
                      if(i<r-1 && rooms[i+1][j]>count+1)
                          q.offer((i+1)*c+j);
                      if(j>0 && rooms[i][j-1]>count+1)
                          q.offer(i*c+(j-1));
                      if(j<c-1 && rooms[i][j+1]>count+1)
                          q.offer(i*c+(j+1));
                  }
              }
          }
      
          public void wallsAndGates(int[][] rooms) {
              if(rooms.length==0)
                  return;
              for(int i=0; i<rooms.length; i++)
                  for(int j=0; j<rooms[0].length; j++)
                      if(rooms[i][j]==0)
                          bfs(rooms, i, j);
          }
      }

  • 0
    A

    There is actually some inefficiency. Consider
    inf inf
    inf 0
    your code will enqueue top left twice.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.