Leetcode 417 Solution

This article provides solution to leetcode question 417 (pacific-atlantic-water-flow)
Categories:
Tags:
Access this page by simply typing in "lcs 417" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/pacific-atlantic-water-flow

Solution

class Solution {
public:
    void fill(vector<vector<int>>& matrix, vector<vector<int>>& a, queue<pair<int, int>>& q, int m, int n)
    {
        while (q.empty() == false)
        {
            auto pair = q.front();
            q.pop();
            int i = pair.first;
            int j = pair.second;

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

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

            if (i > 0 && matrix[i][j] <= matrix[i - 1][j])
            {
                if (a[i - 1][j] == 0)
                {
                    a[i - 1][j] = 1;
                    q.push(make_pair(i - 1, j));
                }
            }

            if (j > 0 && matrix[i][j] <= matrix[i][j - 1])
            {
                if (a[i][j - 1] == 0)
                {
                    a[i][j - 1] = 1;
                    q.push(make_pair(i, j - 1));
                }
            }
        }
    }

    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<pair<int, int>> res;

        if (matrix.size() == 0)
            return res;

        int m = matrix.size();
        int n = matrix[0].size();

        vector<vector<int>> a(m, vector<int>(n));
        vector<vector<int>> b(m, vector<int>(n));

        queue<pair<int, int>> q;

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

        fill(matrix, a, q, m, n);

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

        fill(matrix, b, q, m, n);

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (a[i][j] && b[i][j])
                    res.push_back(make_pair(i, j));
            }
        }

        return res;
    }
};