Welcome to Subscribe On Youtube

Question

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

You are given an m x n grid rooms 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 231 - 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.

 

Example 1:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2:

Input: rooms = [[-1]]
Output: [[-1]]

 

Constraints:

  • m == rooms.length
  • n == rooms[i].length
  • 1 <= m, n <= 250
  • rooms[i][j] is -1, 0, or 231 - 1.

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

  • 
    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) // min check is here in if
                        continue;
                    rooms[x][y] = rooms[p.x][p.y] + 1;
                    queue.offer(new Pair(x, y));
                }
            }
        }
    }
    
    
    ############
    
    class Solution {
        public void wallsAndGates(int[][] rooms) {
            int m = rooms.length;
            int n = rooms[0].length;
            Deque<int[]> q = new LinkedList<>();
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (rooms[i][j] == 0) {
                        q.offer(new int[] {i, j});
                    }
                }
            }
            int d = 0;
            int[] dirs = {-1, 0, 1, 0, -1};
            while (!q.isEmpty()) {
                ++d;
                for (int i = q.size(); i > 0; --i) {
                    int[] p = q.poll();
                    for (int j = 0; j < 4; ++j) {
                        int x = p[0] + dirs[j];
                        int y = p[1] + dirs[j + 1];
                        if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] == Integer.MAX_VALUE) {
                            rooms[x][y] = d;
                            q.offer(new int[] {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);
                    }
                }
            }
        }
    };
    
  • class Solution:
        def wallsAndGates(self, rooms: List[List[int]]) -> None:
            """
            Do not return anything, modify rooms in-place instead.
            """
            m, n = len(rooms), len(rooms[0])
            inf = 2**31 - 1
            q = deque([(i, j) for i in range(m) for j in range(n) if rooms[i][j] == 0])
            d = 0
            while q:
                d += 1
                for _ in range(len(q)):
                    i, j = q.popleft()
                    for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                        x, y = i + a, j + b
                        # bfs so first reaching inf is always the shortest
                        # set its value from inf to d, same as marking as visited
                        if 0 <= x < m and 0 <= y < n and rooms[x][y] == inf:
                            rooms[x][y] = d
                            q.append((x, y))
    
    
    class Solution: # dfs
        def wallsAndGates(self, rooms: List[List[int]]) -> None:
            if not rooms or not rooms[0]:
                return
    
            m, n = len(rooms), len(rooms[0])
            isVisited = [[False] * n for _ in range(m)]  # isVisited map shared among all gates
    
            def fill(i: int, j: int, distance: int) -> None:
                nonlocal m, n
    
                # rooms[i][j] <= 0 meaning == -1 or == 0, both stop
                if i < 0 or i >= m or j < 0 or j >= n or rooms[i][j] <= 0 or isVisited[i][j]:
                    return
    
                rooms[i][j] = min(rooms[i][j], distance)
                isVisited[i][j] = True
    
                fill(i - 1, j, distance + 1)
                fill(i, j + 1, distance + 1)
                fill(i + 1, j, distance + 1)
                fill(i, j - 1, distance + 1)
    
                isVisited[i][j] = False
    
            for i in range(m):
                for j in range(n):
                    if rooms[i][j] == 0:  # start from every gate
                        fill(i, j, 0)
    
    ############
    
    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))
    
    
  • func wallsAndGates(rooms [][]int) {
    	m, n := len(rooms), len(rooms[0])
    	var q [][]int
    	for i := 0; i < m; i++ {
    		for j := 0; j < n; j++ {
    			if rooms[i][j] == 0 {
    				q = append(q, []int{i, j})
    			}
    		}
    	}
    	d := 0
    	dirs := []int{-1, 0, 1, 0, -1}
    	for len(q) > 0 {
    		d++
    		for i := len(q); i > 0; i-- {
    			p := q[0]
    			q = q[1:]
    			for j := 0; j < 4; j++ {
    				x, y := p[0]+dirs[j], p[1]+dirs[j+1]
    				if x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] == math.MaxInt32 {
    					rooms[x][y] = d
    					q = append(q, []int{x, y})
    				}
    			}
    		}
    	}
    }
    

All Problems

All Solutions