Share my Java solution


  • 0

    It's a bit lengthy, but hopefully it's easy to understand. Basically the idea is to walk from each gate in a bfs way, as long as the existing distance is longer than the current bfs level, we update it and continue walk through.

    public class Solution {
      // define the directions
      int[] dx = {-1, 1, 0, 0};
      int[] dy = {0, 0, -1, 1};
      
      public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0 || rooms[0].length == 0)
            return;
            
        int n = rooms.length, m = rooms[0].length;
        
        for (int i = 0; i < n; i++)
          for (int j = 0; j < m; j++)
            // let's walk from the gate in a bfs way
            if (rooms[i][j] == 0) bfs(rooms, n, m, i, j);
      }
      
      void bfs(int[][] rooms, int n, int m, int i, int j) {
        Queue<Integer[]> queue = new LinkedList<>();
        queue.add(new Integer[]{i, j});
        queue.add(null);
        
        // initial level
        int level = 1;
        
        while (!queue.isEmpty()) {
          Integer[] p = queue.poll();
          
          if (p != null) {
            // try 4 directions
            for (int k = 0; k < 4; k++) {
              int x = p[0] + dx[k];
              int y = p[1] + dy[k];
              
              // for a valid room, if its current level is larger, update it
              // and continue walk from it
              if (x >= 0 && x < n && y >= 0 && y < m && rooms[x][y] > level) {
                rooms[x][y] = level;
                queue.add(new Integer[]{x, y});
              }
            }
          } else if (!queue.isEmpty()) {
            // reach a new level
            level++;
            queue.add(null);
          }
        }
      }
    }

Log in to reply
 

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