[LeetCode]Pacific Atlantic Water Flow

BFS的问题，我们只需要分别从上左和下右开始BFS，分别维护两个matrix来记录visited过的cell，找到公共可以到达的cell即可。假设输入矩阵为m * n，时间复杂度O(m * n)，空间复杂度O(m * n)，代码如下：

	class Solution {
	public:
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
	int m = matrix.size(), n = m? matrix[0].size(): 0;
	vector<vector<bool>> visited1(m, vector<bool>(n, false)), visited2(m, vector<bool>(n, false));
	vector<pair<int, int>> res;
	queue<pair<int, int>> q1, q2;
	for(int i = 0; i < m; ++i)
	{
	q1.push({i, 0});
	q2.push({i, n - 1});
	}
	for(int j = 0; j < n; ++j)
	{
	q1.push({0, j});
	q2.push({m - 1, j});
	}
	bfs(matrix, visited1, q1);
	bfs(matrix, visited2, q2);
	for(int i = 0; i < m; ++i)
	{
	for(int j = 0; j < n; ++j)
	{
	if(visited1[i][j] && visited2[i][j])
	res.push_back({i, j});
	}
	}
	return res;
	}
	private:
	void bfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, queue<pair<int, int>>& q)
	{
	int m = matrix.size(), n = m? matrix[0].size(): 0;
	vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	while(q.size())
	{
	auto p = q.front();
	q.pop();
	int i = p.first, j = p.second;
	visited[i][j] = true;
	for(auto&& dir : dirs)
	{
	int x = i + dir.first, y = j + dir.second;
	if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] >= matrix[i][j] && !visited[x][y])
	q.push({x, y});
	}
	}
	}
	};

view raw Pacific Atlantic Water Flow.cpp hosted with ❤ by GitHub