1. Walls and Gates

https://leetcode.com/problems/walls-and-gates/

经典反转思路

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if(m == 0)
        {
            return ;
        }
        int n = rooms[0].size();

        list<pair<int, int>> queue;
        for(int i = 0; i<m; i++)
        {
            for(int j = 0; j<n; j++)
            {
                if(rooms[i][j] == 0)
                {
                    queue.push_back(make_pair(i, j));
                }
            }
        }

        while(!queue.empty())
        {
            pair<int, int> p = queue.front();
            queue.pop_front();

            int dx[] = {0, 1, 0, -1};
            int dy[] = {1, 0, -1, 0};
            for(int i = 0; i<4; i++)
            {
                int nx = p.first + dx[i];
                int ny = p.second + dy[i];

                if(nx < 0 || nx >= m || ny < 0 || ny >= n || rooms[nx][ny] == -1 || rooms[nx][ny] < rooms[p.first][p.second] + 1)
                {
                    continue;
                }

                rooms[nx][ny] = rooms[p.first][p.second] + 1;
                queue.push_back(make_pair(nx, ny));
            }
        }
    }
};