286.Walls and Gates

Tags: [BFS], [trick], [queue], [four_direction]

Com: {fb}, {g}

Link: https://leetcode.com/problems/walls-and-gates/#/description

You are given am x n2D 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 value2^31- 1 = 2147483647to representINFas 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 withINF.

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

Better Solution: BFS

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        if not rooms or not rooms[0]:
            return

        num_of_rows = len(rooms)
        num_of_cols = len(rooms[0])

        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if rooms[row][col] == 0:
                    self.bfs(rooms, num_of_rows, num_of_cols, row, col)

    def bfs(self, rooms, num_of_rows, num_of_cols, start_row, start_col):
        queue = collections.deque()
        queue.append((start_row, start_col))
        while queue:
            row, col = queue.popleft()
            distance = rooms[row][col]

            # iterate four directions
            # top, left, bottom, right
            directions = ((-1, 0), (0, -1), (1, 0), (0, 1))
            for d in directions:
                r, c = row + d[0], col + d[1]
                if 0 <= r < num_of_rows and 0 <= c < num_of_cols and\
                   rooms[r][c] > 0 and rooms[r][c] > distance + 1:
                    rooms[r][c] = distance + 1
                    queue.append((r, c))

Revelation:

• We can use the loop to access four directions.

Solution: BFS

from collections import deque

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        if not rooms or not rooms[0]:
            return

        num_of_rows = len(rooms)
        num_of_cols = len(rooms[0])

        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if rooms[row][col] == 0:
                    self.bfs(rooms, num_of_rows, num_of_cols, row, col)

    def bfs(self, rooms, num_of_rows, num_of_cols, curr_row, curr_col):
        queue = deque()
        queue.append((curr_row, curr_col))
        while queue:
            row, col = queue.popleft()
            distance = rooms[row][col]

            # try four directions
            # top
            if row - 1 >= 0 and rooms[row - 1][col] > distance + 1:
                rooms[row - 1][col] = distance + 1
                queue.append((row - 1, col))

            # left
            if col - 1 >= 0 and rooms[row][col - 1] > distance + 1:
                rooms[row][col - 1] = distance + 1
                queue.append((row, col - 1))

            # bottom
            if row + 1 < num_of_rows and rooms[row + 1][col] > distance + 1:
                rooms[row + 1][col] = distance + 1
                queue.append((row + 1, col))

            # right
            if col + 1 < num_of_cols and rooms[row][col + 1] > distance + 1:
                rooms[row][col + 1] = distance + 1
                queue.append((row, col + 1))

Note:

• Time complexity = O(num_of_gates * (num_of_rows * num_of_cols)).
• Space complexity = O(1).