Leetcode 286 Solution

This article provides solution to leetcode question 286 (walls-and-gates)
Categories:
Tags:
Access this page by simply typing in "lcs 286" in your browser address bar if you have bunnylol configured.

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

Solution

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



        queue<pair<int, int>> q;
        int m = rooms.size();
        int n = rooms[0].size();



        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (rooms[i][j] == 0)
                    q.push(make_pair(i, j));



        while (q.empty() == false)
        {
            auto pos = q.front();
            q.pop();



            int i = pos.first;
            int j = pos.second;



            if (i > 0 && rooms[i - 1][j] == 2147483647)
            {
                rooms[i - 1][j] = rooms[i][j] + 1;
                q.push(make_pair(i - 1, j));
            }



            if (i < m - 1 && rooms[i + 1][j] == 2147483647)
            {
                rooms[i + 1][j] = rooms[i][j] + 1;
                q.push(make_pair(i + 1, j));
            }



            if (j > 0 && rooms[i][j - 1] == 2147483647)
            {
                rooms[i][j - 1] = rooms[i][j] + 1;
                q.push(make_pair(i, j - 1));
            }



            if (j < n - 1 && rooms[i][j + 1] == 2147483647)
            {
                rooms[i][j + 1] = rooms[i][j] + 1;
                q.push(make_pair(i, j + 1));
            }
        }
    }
};