286. Walls and Gates - cocoder39/coco39_LC GitHub Wiki

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])
        queue = collections.deque()

        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    queue.append((0, i, j, ))
        
        while queue:
            dis, row, col = queue.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                newRow, newCol = row+dx, col+dy
                if 0 <= newRow < m and 0 <= newCol < n and rooms[newRow][newCol] > dis + 1:
                    rooms[newRow][newCol] = dis + 1
                    queue.append((dis+1, newRow, newCol))

void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if (m == 0)
            return;
        int n = rooms[0].size();
        queue<pair<int, int>> q;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0)
                    q.push({i, j});
            } 
        }
        
        vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (! q.empty()) {
            auto pos = q.front();
            q.pop();
            
            for (auto dir : dirs) {
                int x = pos.first + dir[0];
                int y = pos.second + dir[1];
                if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] > rooms[pos.first][pos.second] + 1) {
                    rooms[x][y] = rooms[pos.first][pos.second] + 1;
                    q.push({x, y});
                }
            }
        }
    }

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        m = rooms.size();
        if (m == 0) return;
        n = rooms[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    helper(rooms, i, j);
                }
            }
        }
        
    }
private:    
    const vector<pair<int, int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    
    void helper(vector<vector<int>>& rooms, int row, int col) {
        for (auto dir : dirs) {
            int r = row + dir.first;
            int c = col + dir.second;
            if (r >= 0 && r < m && c >= 0 && c < n && rooms[r][c] - 1 > rooms[row][col]) {
                rooms[r][c] = rooms[row][col] + 1;
                helper(rooms, r, c);
            }
        } 
    }
};

.GGGGGGGGGGGGGGG
................
GGGGGGGGGGGGGGG.
................
.GGGGGGGGGGGGGGG
................
GGGGGGGGGGGGGGG.
................
.GGGGGGGGGGGGGGG
................
GGGGGGGGGGGGGGG.
................
.GGGGGGGGGGGGGGG
................
GGGGGGGGGGGGGGG.
................