Leetcode第695题. Max Area of Island

本是古典 何须时尚 2022-06-05 10:22 270阅读 0赞

原题地址如下：https://leetcode.com/problems/max-area-of-island/description/
这里写图片描述

使用深度优先搜索的方案

  1. class Solution {
  2. public:
  3.     int maxAreaOfIsland(vector<vector<int>>& grid) {
  4.         int m = grid.size(), n = grid[0].size(), ans = 0;
  5.         for (int i = 0; i < m; i++) 
  6.             for (int j = 0; j < n; j++) 
  7.                 if (grid[i][j] == 1) ans = max(ans, dfs(grid, i, j));//当前结点的值为1才深度优先遍历
  8.         return ans;
  9.     }
  10. private:
  11.     int dfs(vector<vector<int>>& grid, int row, int col) {
  12.         int m = grid.size(), n = grid[0].size(), area = 1;//一旦进入 因为当前结点的值为1 首先将其对应的area设为1
  13.         grid[row][col] = 0;//将这个点的值设为2 因为这个点已经被处理过了  
  15.         vector<int> dir({-1,0,1,0,-1});//这是一个巧妙的设置遍历上下左右的点的方式 减少代码书写
  16.         for (int i = 0; i < 4; i++) {
  17.             int r = row+dir[i], c = col+dir[i+1];//依次遍历当前处理结点的上，右，下，左四个点
  18.             if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) //结点在范围内 且该节点的值为1 排除所有为0的点以及访问过的点 避免重复
  19.                 area += dfs(grid, r, c);
  20.         }
  21.         return area;
  22.     }
  23. };

这道题目的关键在于设置当前结点的面积area的计算方案上。在遍历四周结点的同时，需要考虑到排除重复搜索的问题：

  1. 如果当前结点值为0 直接跳过。
  2. 如果当前结点的值为2（任意不为1值）代表这个结点已经在之前处理过了：有可能是直接遍历过了这个点，也有可能是在求解其他的点的面积的时候遍历过了这个点。总之这些点是属于其他的联通集合，我们就不需要再对这些点进行处理。一个是减少搜索的重复，二是可以直接避免重复计算。

发表评论

表情：
评论列表 （有 0 条评论，270人围观）

还没有评论，来说两句吧...

相关阅读