效果图网站排行榜前十名,wordpress给文章设置标题,常州网站建设公司哪个好,如何用c 做网站背景1. 题目链接#xff1a;695. 岛屿的最大面积
2. 题目描述#xff1a; 给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合#xff0c;这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都…1. 题目链接695. 岛屿的最大面积
2. 题目描述 给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0代表水包围着。 岛屿的面积是岛上值为 1 的单元格的数目。 计算并返回 grid 中最大的岛屿面积。如果没有岛屿则返回面积为 0 。 示例 1 输入grid [[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 输入grid [[0,0,0,0,0,0,0,0]]
输出0提示 m grid.lengthn grid[i].length1 m, n 50grid[i][j] 为 0 或 1 3. 解法递归
3.1 算法思路
遍历整个矩阵每当遇到一块土地的时候就用深度优先遍历或者宽度优先遍历将与这块土地相连的整个岛屿的面积计算出出来然后在搜索得到的所有岛屿面积求一个最大值即可在搜索过程中为了防止搜到重复的土地 可以开一个同等规模的布尔数组标记以下这个位置是否已经被访问过也可以将原始矩阵的1修改成0但是这样的操作会修改原始矩阵
3.2 算法流程
主函数内
遍历整个数组发现一块没有遍历到的土地之后就用dfs将于这块土地相连的岛屿的面积求出来然后将面积更新到最终结果ret中
深度搜索dfs中
能够进到dfs函数中说明是一个没遍历到的位置标记一下已经遍历过设置一个变量count记录最终的面积上下左右遍历四个位置如果找到一块没有遍历到的土地就将这块土地相连的岛屿面积累加到count上循环结束后count中存的就是这块岛屿的面积返回即可
3.3 C算法代码
class Solution {bool vis[51][51]; // 访问标记数组用于记录某个位置是否已经访问过int m, n; // 网格的行数和列数int dx[4] {0, 0, 1, -1}; // x轴方向的偏移量int dy[4] {1, -1, 0, 0}; // y轴方向的偏移量int count; // 当前岛屿的面积
public:// 计算给定网格中最大的岛屿面积int maxAreaOfIsland(vectorvectorint grid) {m grid.size(), n grid[0].size();int ret 0; // 最大岛屿面积for (int i 0; i m; i) {for (int j 0; j n; j) {if (!vis[i][j] grid[i][j] 1) { // 如果当前位置未被访问且为陆地count 0; // 重置岛屿面积dfs(grid, i, j); // 进行深度优先搜索ret max(ret, count); // 更新最大岛屿面积}}}return ret; // 返回最大岛屿面积}// 深度优先搜索函数用于计算岛屿面积void dfs(vectorvectorint grid, int i, int j) {count; // 当前位置为陆地岛屿面积加一vis[i][j] true; // 标记当前位置已访问for (int k 0; k 4; k) { // 遍历四个方向int x i dx[k], y j dy[k]; // 计算下一个位置的坐标if (x 0 x m y 0 y n !vis[x][y] grid[x][y] 1) { // 如果下一个位置在网格范围内且未被访问且为陆地dfs(grid, x, y); // 继续深度优先搜索}}}
};
