Wednesday, September 30, 2015

Leetcode: 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
Understand the problem:
It is very classic backtracking problem. We can start from each gate (0 point), and searching for its neighbors. We can either use DFS or BFS solution.

A DFS Solution:
public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }
        
        int m = rooms.length;
        int n = rooms[0].length;
        
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    wallsAndGatesHelper(i, j, 0, visited, rooms);
                }
            }
        }
    }
    
    private void wallsAndGatesHelper(int row, int col, int distance, boolean[][] visited, int[][] rooms) {
        int rows = rooms.length;
        int cols = rooms[0].length;
        
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return;
        }
        
        // visited
        if (visited[row][col]) {
            return;
        }
        
        // Is wall?
        if (rooms[row][col] == -1) {
            return;
        }
        
        // Distance greater than current
        if (distance > rooms[row][col]) {
            return;
        }
        
        
        // Mark as visited
        visited[row][col] = true;
        
        if (distance < rooms[row][col]) {
            rooms[row][col] = distance;
        }
        
        // go up, down, left and right
        wallsAndGatesHelper(row - 1, col, distance + 1, visited, rooms);
        wallsAndGatesHelper(row + 1, col, distance + 1, visited, rooms);
        wallsAndGatesHelper(row, col - 1, distance + 1, visited, rooms);
        wallsAndGatesHelper(row, col + 1, distance + 1, visited, rooms);
        
        // Mark as unvisited
        visited[row][col] = false;
    }
}

A BFS Solution:
public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }
        
        int m = rooms.length;
        int n = rooms[0].length;
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    wallsAndGatesHelper(i, j, 0, rooms, queue);
                }
            }
        }
    }
    
    private void wallsAndGatesHelper(int row, int col, int distance, int[][] rooms, Queue<Integer> queue) {
        fill(row, col, distance, rooms, queue);
        
        int m = rooms.length;
        int n = rooms[0].length;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cord = queue.poll();
                int x = cord / n;
                int y = cord % n;
            
                fill(x - 1, y, distance + 1, rooms, queue);
                fill(x + 1, y, distance + 1, rooms, queue);
                fill(x, y - 1, distance + 1, rooms, queue);
                fill(x, y + 1, distance + 1, rooms, queue);
            
            }
            distance++;
        }
    }
    
    private void fill (int row, int col, int distance, int[][] rooms, Queue<Integer> queue) {
        int m = rooms.length;
        int n = rooms[0].length;
        
        if (row < 0 || row >= m || col < 0 || col >= n) {
            return;
        }
        
        if (rooms[row][col] == -1) {
            return;
        }
        
        if (distance > rooms[row][col]) {
            return;
        }
        
        if (distance < rooms[row][col]) {
            rooms[row][col] = distance;
        }
        
        int cord = row * n + col;
        queue.offer(cord);
    }
}

2 comments:

  1. why not put all gate cells into the queue at the beginning and then BFS the matrix. it is simpler in logic and guarantees O(m*n) complexity

    ReplyDelete
    Replies
    1. What do you mean by putting all gate cells into beginning queue? The queue here is used to store the updated room point. Also, in order to get all the gates, you need at least to visit all the point in matrix rooms. This is exactly what has been done in the wallsAndGates(). So I think the BFS here is correct at this point.

      Delete