663. Walls and Gates

Code(Language:C++)

class Solution {
public:
    /**
     * @param rooms: m x n 2D grid
     * @return: nothing
     */
    struct node{
        int x, y; 
        node(int a, int b){
            x = a; 
            y = b; 
        }
    };
    const vector<int> dx = {-1, 1, 0, 0};
    const vector<int> dy = {0, 0, -1, 1}; 
    const int dir = 4; 
    void wallsAndGates(vector<vector<int>> &rooms) {
        // write your code here
        //BFS 层层剥洋葱；target入栈;全部target入栈
        const int m = rooms.size();
        if(m == 0){
            return; 
        }
        const int n = rooms[0].size();
        std::queue<node> q;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(rooms[i][j] == 0){
                    q.push(node(i, j)); 
                }
            }
        }
        // BFS with queue 模板
        while(!q.empty()){
            int sizeQ = q.size();
            for(int i = 0; i < sizeQ; i++){
                node oldN = q.front();
                q.pop(); 
                for(int j = 0; j < dir; j++){
                    int newX = oldN.x + dx[j];
                    int newY = oldN.y + dy[j]; 
                    if(newX < 0 || newX >= m || newY < 0 || newY >= n || rooms[newX][newY] == -1 || rooms[newX][newY] != INT_MAX){
                        continue; 
                    }
                    //操作在这里
                    rooms[newX][newY] = rooms[oldN.x][oldN.y] + 1; 
                    //新入栈
                    q.push(node(newX, newY)); 
                }
            }
        }
        return; 
    }
};