Question

Formatted question description: https://leetcode.ca/all/286.html

 286	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 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

 @similar: 317	Shortest Distance from All Buildings

Algorithm

Search for the position of 0, and every time a 0 is found, start DFS traversal with four adjacent points around it as the starting point, and bring in the depth value 1.

If the value encountered is greater than the current depth value, assign the position value to the current depth value, and start DFS traversal for the four adjacent points of the current point. Note that the depth value needs to be increased by 1.

After the traversal is completed, all positions are updated correctly

Code

Java

public class Solution_dfs {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
            return;
        }

        int m = rooms.length;
        int n = rooms[0].length;


        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) { // start from every gate
                    boolean[][] isVisited = new boolean[m][n]; // each new gate, associated with a new isVisited map

                    fill(rooms, i, j, 0, isVisited);
                }
            }
        }
    }

    public void fill(int[][] rooms, int i, int j, int distance, boolean[][] isVisited) {
        int m = rooms.length;
        int n = rooms[0].length;

        // rooms[i][j] <= 0 meaning == -1 or == 0, both stop
        if (i < 0 || i >= m || j < 0 || j >= n || rooms[i][j] <= 0 || isVisited[i][j]) {
            return;
        }

        rooms[i][j] = Math.min(rooms[i][j], distance);
        isVisited[i][j] = true;

        fill(rooms, i - 1, j, distance + 1, isVisited);
        fill(rooms, i, j + 1, distance + 1, isVisited);
        fill(rooms, i + 1, j, distance + 1, isVisited);
        fill(rooms, i, j - 1, distance + 1, isVisited);

        isVisited[i][j] = false;
    }
}


public class Solution_bfs {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) return;
        int[][] dir = new int[][]{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

        Queue<Pair> queue = new LinkedList<>();

        for (int i = 0; i < rooms.length; i++) {
            for (int j = 0; j < rooms[0].length; j++) {
                if (rooms[i][j] == 0) {
                    queue.offer(new Pair(i, j));
                }
            }
        }

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            for (int[] d : dir) {
                int x = p.x + d[0];
                int y = p.y + d[1];
                if (x < 0 || x >= rooms.length || y < 0 || y >= rooms[0].length
                    || rooms[x][y] <= rooms[p.x][p.y] + 1)
                    continue;
                rooms[x][y] = rooms[p.x][p.y] + 1;
                queue.offer(new Pair(x, y));
            }
        }
    }
}

// OJ: https://leetcode.com/problems/walls-and-gates/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    void wallsAndGates(vector<vector<int>>& A) {
       int M = A.size(), N = A[0].size(), dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; 
        queue<pair<int, int>> q;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) q.emplace(i, j);
            }
        }
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto [x, y] = q.front();
                q.pop();
                for (auto &[dx, dy] : dirs) {
                    int a = x + dx, b = y + dy;
                    if (a < 0 || b < 0 || a >= M || b >= N || A[a][b] <= A[x][y] + 1) continue; 
                    A[a][b] = A[x][y] + 1;
                    q.emplace(a, b);
                }
            }
        }
    }
};

from collections import deque

INF = 2147483647


class Solution(object):
  def wallsAndGates(self, rooms):
    """
    :type rooms: List[List[int]]
    :rtype: void Do not return anything, modify rooms in-place instead.
    """
    queue = deque([])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(0, len(rooms)):
      for j in range(0, len(rooms[0])):
        if rooms[i][j] == 0:
          queue.append((i, j))

    while queue:
      i, j = queue.popleft()
      for di, dj in directions:
        p, q = i + di, j + dj
        if 0 <= p < len(rooms) and 0 <= q < len(rooms[0]) and rooms[p][q] == INF:
          rooms[p][q] = rooms[i][j] + 1
          queue.append((p, q))

286 - Walls and Gates

Question

Algorithm

Code

All Problems

All Solutions