常规的dfs题目,使用位运算标记两个状态,1和2同时命中就是3
C++ 代码
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
m_ = heights.size(), n_ = heights[0].size();
heights_ = heights;
st_ = vector<vector<bool>>(m_, vector<bool>(n_, false));
res_ = vector<vector<int>>(m_, vector<int>(n_, 0));
queue<pair<int,int>> q;
//init pacific
int flag = 1;
for(int i=0; i<m_; ++i) {
st_[i][0] = true;
res_[i][0] = res_[i][0]|flag;
q.push({i,0});
}
for(int j=0; j<n_; ++j) {
st_[0][j] = true;
res_[0][j] = res_[0][j]|flag;
q.push({0,j});
}
dfs(q, flag);
// init atlantic
flag = 2;
st_ = vector<vector<bool>>(m_, vector<bool>(n_, false));
q = queue<pair<int,int>>();
for(int i=0; i<m_; ++i) {
st_[i][n_-1] = true;
res_[i][n_-1] = res_[i][n_-1]|flag;
q.push({i,n_-1});
}
for(int j=0; j<n_; ++j) {
st_[m_-1][j] = true;
res_[m_-1][j] = res_[m_-1][j]|flag;
q.push({m_-1,j});
}
dfs(q, flag);
vector<vector<int>> ans;
for(int i=0; i<m_; ++i) {
for(int j=0; j<n_; ++j) {
if(res_[i][j] == 3) ans.push_back({i,j});
}
}
return ans;
}
private:
int m_, n_;
vector<vector<int>> heights_;
vector<vector<bool>> st_;
vector<vector<int>> res_;
void dfs(queue<pair<int,int>> &q, int flag) {
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1,0, -1, 0};
while(q.size()) {
auto t = q.front();
q.pop();
for(int d=0; d<4; ++d) {
int x = t.first + dx[d], y = t.second + dy[d];
if(0<=x && x<m_ && 0<=y && y<n_ && !st_[x][y] && heights_[x][y] >= heights_[t.first][t.second]) {
res_[x][y] = res_[x][y] | flag;
st_[x][y] = true;
q.push({x,y});
}
}
}
}
};