• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

417. 太平洋大西洋水流问题

有一个m n的长方形岛屿,毗邻太平洋和大西洋。“太平洋”位于大陆的左上边,“大西洋”位于大陆的右下边。

这个岛被分成一个个方形格子。给定m x n heights的整数矩阵,heights[r][c]表示坐标(r,c)上的像元高于海平面的高度。

这个岛上雨水很多。如果相邻单元的高度小于或等于当前单元的高度,雨水可以直接流向北、南、东、西相邻单元。水可以从海洋附近的任何细胞流入海洋。

返回格网坐标结果的2D列表,其中result=[ri,ci]表示雨水从像元(ri,ci)流向太平洋和大西洋。

示例1:

on0zdvcaznp4334.jpg

输入:高度=[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2]

输出: [[0,4]、[1,3]、[1,4]、[2,2]、[3,0]、[3,1]、[4,0]]

示例2:

输入: heights=[[2,1],[1,2]]

输出: [[0,0]、[0,1]、[1,0]、[1,1]]

提示:

m==高度.长度

n==heights[r]。长度

1=m,n=200

0=高度[r][c]=105

1 #包括iostream

2 #包含向量

3 #包含算法

4 #包含字符串

5 #包含无序映射

6 #包含无序集

7 #包含队列

8使用命名空间std

10级解决方案{

11 public:

12 /*题目的意思是从任意坐标位置都可以最终到达太平洋(上边界和左边界)和大西洋(右边界和下边界)。

3 * 1,可以到达上、左、右、下边界点,所有边界点都可以排队;

14 * 2.BFS以任意边界点为起点,寻找与边界相连的所有点;

15 * 3.返回所有符合条件的坐标;

16 */

7//上下左右四个方向

18 vectorstd:pairint,int g _ direction={ { {-1,0},{0,1},{1,0},{0,-1 } };

19 void pushToqueue(int x,int y,int mask,queuestd:pairint,int q,vectorvectorint已访问){

20 visited[x][y]|=(1 mask);//根据掩码(1-太平洋,2-大西洋)刷新受访者

21 q.push(make_pair(x,y));

22 }

23 //根据面罩标记检查是连接太平洋还是大西洋

24 bool check(const vector vector visited,int x,int y,int mask) {

25返回((已访问[x][y] (1个掩码))!=0);

26 }

27矢量矢量pacificAtlantic(矢量矢量高度){

2

8 vector<vector<int>> ans; 29 if (heights.size() == 0 || heights[0].size() == 0) { 30 return ans; 31 } 32 int row = heights.size(); 33 int col = heights[0].size(); 34 /* visited存储与两个洋连通情况: 35 * 0-表示与两个洋均不连通; 36 * 1-表示与太平洋连通; 37 * 2-表示与大西洋连通; 38 * 3-表示既与太平洋 39 */ 40 vector<vector<int>> visited(row, vector<int>(col, 0)); 41 queue<std::pair<int, int>> q; 42 constexpr int pacificMask = 0; // 0-太平洋 43 constexpr int atlanticMask = 1; // 1-大西洋 44 // 将左边界和右边界点入队 45 for (int i = 0; i < row; i++) { 46 pushToqueue(i, 0, pacificMask, q, visited); // 与太平洋连通 47 pushToqueue(i, col - 1, atlanticMask, q, visited); // 与大西洋连通 48 } 49 // 将上边界和下边界入队 50 for (int j = 0; j < col; j++) { 51 pushToqueue(0, j, pacificMask, q, visited); // 与太平洋连通 52 pushToqueue(row - 1, j, atlanticMask, q, visited); // 与大西洋连通 53 } 54 while (!q.empty()) { 55 int curX = q.front().first; 56 int curY = q.front().second; 57 q.pop(); 58 for (auto &pair : g_direction) { 59 60 int xNext = curX + pair.first; 61 int yNext = curY + pair.second; 62 if (xNext < 0 || xNext >= row || yNext < 0 || yNext >= col) { 63 continue; 64 } 65 if (heights[curX][curY] > heights[xNext][yNext]) { 66 continue; 67 } 68 if (check(visited, curX, curY, pacificMask) && !check(visited, xNext, yNext, pacificMask)) { 69 pushToqueue(xNext, yNext, pacificMask, q, visited); 70 } 71 if (check(visited, curX, curY, atlanticMask) && !check(visited, xNext, yNext, atlanticMask)) { 72 pushToqueue(xNext, yNext, atlanticMask, q, visited); 73 } 74 } 75 } 76 for (int i = 0; i < row; i++) { 77 for (int j = 0; j < col; j++) { 78 if (visited[j] == 3) { 79 ans.push_back({i, j}); 80 } 81 } 82 } 83 // 打印输出结果: 84 for (auto &pair : ans) { 85 std::cout << pair[0] << "," << pair[1] << endl; 86 } 87 std::cout << endl; 88 return ans; 89 } 90 }; 91 int main() 92 { 93 /* 94 * 测试用例1: 95 /* 输入:heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] 96 * 期望输出:[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] 97 */ 98 vector<vector<int>> grid = { 99 {1, 2, 2, 3, 5}, 100 {3, 2, 3, 4, 4}, 101 {2, 4, 5, 3, 1}, 102 {6, 7, 1, 4, 5}, 103 {5, 1, 1, 2, 4}}; 104 Solution *test = new Solution(); 105 test->pacificAtlantic(grid); 106 return 0; 107 }
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now