# Untitled

unknown
plain_text
10 days ago
3.8 kB
2
Indexable
Never
```class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
vector<vector<int>> result;
queue<pair<int,int>> BFS;
queue<pair<int,int>> BFS2;
bool pacific[250][250] = {false};
bool atlantic[250][250] = {false};

for(int i = 0; i < heights.size(); i++) {
BFS.push(pair<int, int>(i, 0));
pacific[i][0] = true;
BFS2.push(pair<int, int>(i, int(heights[i].size()) - 1));
atlantic[i][int(heights[i].size()) - 1] = true;
}
for(int j = 0; j < heights[0].size(); j++) {
BFS.push(pair<int, int>(0, j));
pacific[0][j] = true;
BFS2.push(pair<int, int>(int(heights.size()) - 1, j));
atlantic[int(heights.size()) - 1][j] = true;
}

while(!BFS.empty()) {
pair<int, int> t = BFS.front();
BFS.pop();
if(t.first - 1 >= 0 && !pacific[t.first - 1][t.second] && heights[t.first - 1][t.second] >= heights[t.first][t.second]) {
BFS.push(pair<int,int>(t.first - 1, t.second));
pacific[t.first - 1][t.second] = true;
}
if(t.first + 1 < heights.size() && !pacific[t.first + 1][t.second] && heights[t.first + 1][t.second] >= heights[t.first][t.second]) {
BFS.push(pair<int,int>(t.first + 1, t.second));
pacific[t.first + 1][t.second] = true;
}
if(t.second - 1 >= 0 && !pacific[t.first][t.second - 1] && heights[t.first][t.second - 1] >= heights[t.first][t.second]) {
BFS.push(pair<int,int>(t.first, t.second - 1));
pacific[t.first][t.second - 1] = true;
}
if(t.second + 1 < heights[0].size() && !pacific[t.first][t.second + 1] && heights[t.first][t.second + 1] >= heights[t.first][t.second]) {
BFS.push(pair<int,int>(t.first, t.second + 1));
pacific[t.first][t.second + 1] = true;
}
}

while(!BFS2.empty()) {
pair<int, int> t = BFS2.front();
BFS2.pop();
if(t.first - 1 >= 0 && !atlantic[t.first - 1][t.second] && heights[t.first - 1][t.second] >= heights[t.first][t.second]) {
BFS2.push(pair<int,int>(t.first - 1, t.second));
atlantic[t.first - 1][t.second] = true;
}
if(t.first + 1 < heights.size() && !atlantic[t.first + 1][t.second] && heights[t.first + 1][t.second] >= heights[t.first][t.second]) {
BFS2.push(pair<int,int>(t.first + 1, t.second));
atlantic[t.first + 1][t.second] = true;
}
if(t.second - 1 >= 0 && !atlantic[t.first][t.second - 1] && heights[t.first][t.second - 1] >= heights[t.first][t.second]) {
BFS2.push(pair<int,int>(t.first, t.second - 1));
atlantic[t.first][t.second - 1] = true;
}
if(t.second + 1 < heights[0].size() && !atlantic[t.first][t.second + 1] && heights[t.first][t.second + 1] >= heights[t.first][t.second]) {
BFS2.push(pair<int,int>(t.first, t.second + 1));
atlantic[t.first][t.second + 1] = true;
}

}
vector<pair<int, int>> result2;
for(int i = 0; i < heights.size(); i++)
for(int j = 0; j < heights[0].size(); j++)
if(pacific[i][j] && atlantic[i][j])
result2.push_back(pair<int,int>(i,j));
for(int i = 0; i < result2.size(); i++) {
vector<int> tmp;
tmp.push_back(result2[i].first);
tmp.push_back(result2[i].second);
result.push_back(tmp);
}
return result;
}
};```