<filename>scripts/leetcode/amzn/wallsNgates.py
"""

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]]
Example 3:

Input: rooms = [[2147483647]]
Output: [[2147483647]]
Example 4:

Input: rooms = [[0]]
Output: [[0]]
 

Constraints:

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

"""


class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        if not rooms:
            return []
        row = len(rooms)
        col = len(rooms[0])

        q = collections.deque()

        for idx in range(row):
            for jdx in range(col):
                if rooms[idx][jdx] == 0:
                    q.append((idx, jdx))
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        while q:
            x, y = q.popleft()
            distance = rooms[x][y]+1
            for dx, dy in dirs:
                new_x = dx+x
                new_y = dy+y
                if 0 <= new_x < row and 0 <= new_y < col and rooms[new_x][new_y] == 2147483647:
                    rooms[new_x][new_y] = distance
                    q.append((new_x, new_y))
        return rooms

<filename>scripts/leetcode/amzn/wallsNgates.py
"""

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]]
Example 3:

Input: rooms = [[2147483647]]
Output: [[2147483647]]
Example 4:

Input: rooms = [[0]]
Output: [[0]]
 

Constraints:

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

"""


class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        if not rooms:
            return []
        row = len(rooms)
        col = len(rooms[0])

        q = collections.deque()

        for idx in range(row):
            for jdx in range(col):
                if rooms[idx][jdx] == 0:
                    q.append((idx, jdx))
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        while q:
            x, y = q.popleft()
            distance = rooms[x][y]+1
            for dx, dy in dirs:
                new_x = dx+x
                new_y = dy+y
                if 0 <= new_x < row and 0 <= new_y < col and rooms[new_x][new_y] == 2147483647:
                    rooms[new_x][new_y] = distance
                    q.append((new_x, new_y))
        return rooms

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]] Example 3:  Input: rooms = [[2147483647]] Output: [[2147483647]] Example 4:  Input: rooms = [[0]] Output: [[0]]    Constraints:  m == rooms.length n == rooms[i].length 1 <= m, n <= 250 rooms[i][j] is -1, 0, or 231 - 1. Do not return anything, modify rooms in-place instead.