当前位置:首页 » 《随便一记》 » 正文

力扣(LeetCode)417. 太平洋大西洋水流问题(2023.02.19)

16 人参与  2023年02月21日 11:29  分类 : 《随便一记》  评论

点击全文阅读


有一个 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:    vector<vector<int>> heights;    void bfs(int row, int col, vector<vector<bool>> & ocean) {        if (ocean[row][col]) {            return;        }        int m = heights.size();        int n = heights[0].size();        ocean[row][col] = true;        queue<pair<int, 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);                }            }        }    }    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {        this->heights = heights;        int m = heights.size();        int n = heights[0].size();        vector<vector<bool>> pacific(m, vector<bool>(n, false));        vector<vector<bool>> atlantic(m, vector<bool>(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);        }        vector<vector<int>> result;        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (pacific[i][j] && atlantic[i][j]) {                    vector<int> cell;                    cell.emplace_back(i);                    cell.emplace_back(j);                    result.emplace_back(cell);                }            }        }        return result;    }};

点击全文阅读


本文链接:http://zhangshiyu.com/post/53335.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 冬季宜密雪:结局+番外精编之作(季雯,江随筝)完整章节列表_笔趣阁
  • 完结文末日重生我囤十亿物资杀穿尸潮列表_完结文末日重生我囤十亿物资杀穿尸潮(林野苏晴)
  • 小说江诗云路明哲小说已更新+番外篇章(年少的爱终将散去)纯净阅读
  • 真千金伪装大学生在自家公司实习让狗爬后一口气看完_宋氏小林小姑娘高分神作_小说后续在线阅读_无删减免费完结_
  • 萧逸尘,楚璃,叶紫嫣爱恨决绝,此生不见番外(爱恨决绝,此生不见)TXT+后续+结局在线阅读
  • 假千金要交换人生?我抱着空间做首富爽文_苏木青赵景城虐心反转_小说后续在线阅读_无删减免费完结_
  • 温时雨谢远之续集(清风难渡无缘人)全本完整免费版_起点章节+后续(温时雨谢远之)
  • 订婚两个月后,未婚夫要摆脱包办婚姻精心打造_肖明宝宝宾客故事会_小说后续在线阅读_无删减免费完结_
  • 霍景琛,苏晚,林深昔年请深如海,终不敌薄凉附加(霍景琛,苏晚,林深)(昔年请深如海,终不敌薄凉)全本浏览阅读连载中
  • 新章速递汤安甯,白子奕,汤贝贝是什么小说(结婚十年,回归家庭的老婆在外有二胎了)完本阅读无广告(结婚十年,回归家庭的老婆在外有二胎了)
  • 娇牛马导师偷我论文99篇成功升博导,我让他牢底坐穿精校文本_周老师师姐师兄爽文_小说后续在线阅读_无删减免费完结_
  • 独家顾宇,罗薇:结局+番外精编之作(资助生装阔气,我可不参加)电子书畅享阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1