深圳东莞的网站建设公司,怎么建设自己网站的后台,wordpress导航条,自学学网页设计有一个 m n 的矩形岛屿#xff0c;与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界#xff0c;而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights #xff0c; heights[r][c]…有一个 m × n 的矩形岛屿与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多如果相邻单元格的高度 小于或等于 当前单元格的高度雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 其中 result[i] [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
示例 1 输入: 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]] 输出: [[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 heights.length n heights[r].length 1 m, n 200 0 heights[r][c] 105 来源力扣LeetCode 链接https://leetcode.cn/problems/pacific-atlantic-water-flow
方法一DFS
C提交内容
static const int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};class Solution {
public:vectorvectorint heights;void bfs(int row, int col, vectorvectorbool ocean) {if (ocean[row][col]) {return;}int m heights.size();int n heights[0].size();ocean[row][col] true;queuepairint, int qu;qu.emplace(row, col);while (!qu.empty()) {auto [row, col] qu.front();qu.pop();for (int i 0; i 4; i) {int newRow row dirs[i][0], newCol col dirs[i][1];if (newRow 0 newRow m newCol 0 newCol n heights[newRow][newCol] heights[row][col] !ocean[newRow][newCol]) {ocean[newRow][newCol] true;qu.emplace(newRow, newCol);}}}}vectorvectorint pacificAtlantic(vectorvectorint heights) {this-heights heights;int m heights.size();int n heights[0].size();vectorvectorbool pacific(m, vectorbool(n, false));vectorvectorbool atlantic(m, vectorbool(n, false));for (int i 0; i m; i) {bfs(i, 0, pacific);}for (int j 1; j n; j) {bfs(0, j, pacific);}for (int i 0; i m; i) {bfs(i, n - 1, atlantic);}for (int j 0; j n - 1; j) {bfs(m - 1, j, atlantic);}vectorvectorint result;for (int i 0; i m; i) {for (int j 0; j n; j) {if (pacific[i][j] atlantic[i][j]) {vectorint cell;cell.emplace_back(i);cell.emplace_back(j);result.emplace_back(cell);}}}return result;}
};
