【奇技淫巧】-- 岛屿的最大面积
发布日期:2021-06-30 19:45:56
浏览次数:2
分类:技术文章
本文共 1770 字,大约阅读时间需要 5 分钟。
岛屿的最大面积
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/max-area-of-island
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路(超过99.80%)
第一眼看到,吓得我不敢动,因为DFS我不熟。
放了一天,简单题刷完之后,还是得面对。 其实没那么恐怖,递归回溯,遍历到一个节点就给它置空掉,并计数。代码实现
int checkIsland(vector>& grid, int x, int y) { int count = 0; if (grid[x][y] == 0) return count; else { grid[x][y] = 0; count++; //上 if (x - 1 >= 0) count += checkIsland(grid, x - 1, y); //右 if ((y + 1) < grid[0].size()) count += checkIsland(grid, x, y + 1); //下 if ((x + 1) < grid.size()) count += checkIsland(grid, x + 1, y); //左 if ((y - 1) >= 0) count += checkIsland(grid, x, y - 1); } return count; } int maxAreaOfIsland(vector >& grid) { if (grid.size() == 0) return 0; int max = 0; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { int temp = checkIsland(grid, i, j); if (temp > max) { max = temp; } } } return max; }
转载地址:https://lion-wu.blog.csdn.net/article/details/107691373 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月12日 15时32分42秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
CodeForces - 996D Suit and Tie (暴力)
2019-04-30
ACM 2017 香港区域赛 E - Base Station Sites(二分)
2019-04-30
ACM 2018 青岛区域赛 J-Books (模拟)
2019-04-30
ACM 2016 沈阳区域赛 E - Counting Cliques (dfs)
2019-04-30
ACM 2017 北京区域赛 J-Pangu and Stones(区间dp)
2019-04-30
HDU - 5643 King's Game (约瑟夫环变式)
2019-04-30
UVA - 1452 Jump (约瑟夫环变式)
2019-04-30
POJ - 3517 And Then There Was One (约瑟夫环变式)
2019-04-30
HDU - 2068 RPG的错排 (错排+组合数)
2019-04-30
CodeForces 591C Median Smoothing(思维 模拟)
2019-04-30
升级yosemite后java出错的解决
2019-04-30
03-TCP和UDP的基本认识
2019-04-30
04-TCP三握四挥
2019-04-30
05-TCP的重传机制
2019-04-30
06-TCP的流量控制,拥塞控制
2019-04-30
07-Http的基础知识
2019-04-30
08-HTTPS与加密
2019-04-30
09-其它
2019-04-30
7月区块链行业精选研报合集 | 互链七月研报汇
2019-04-30
互链月报|7月区块链私募融资月报:金额环比增长12.6%,中国市场开始升温
2019-04-30