Max Area of Island（C++岛屿的最大面积）

分手后的思念是犯贱 2022-11-06 12:51 173阅读 0赞

解题思路：

（1）利用栈(stack)来进行深度遍历(dfs)

class Solution {
    public:
        
        void helper(vector<int> &v,vector<vector<int>> &d,vector<int> &vis,vector<vector<int>>& grid,
                    stack<pair<int,int>> &s,int x,int y,int m,int n,int &sum) {
            sum += grid[x][y];
            vis[x*n+y] = 1;
            for(int i=0;i<d.size();i++) {
                if(0<=x+d[i][0] && x+d[i][0]<m && 0<=y+d[i][1] && 
                   y+d[i][1]<n && grid[x+d[i][0]][y+d[i][1]]==1 && vis[(x+d[i][0])*n+y+d[i][1]]==0) {
                    s.push(pair(x+d[i][0],y+d[i][1]));
                } 
            }
            while(!s.empty()) {
                auto temp = s.top();
                s.pop();
                if(vis[temp.first*n+temp.second]==0)
                    helper(v,d,vis,grid,s,temp.first,temp.second,m,n,sum);
            }
            v.push_back(sum);
            return;
        }
        
        int maxAreaOfIsland(vector<vector<int>>& grid) {
            int m = grid.size(),n=grid[0].size();
            vector<int> v;
            vector<int> vis(m*n,0);
            vector<vector<int>> d={
       {1,0},{-1,0},{0,1},{0,-1}};
            int sum = 0;
            for(int i=0;i<grid.size();i++) {
                for(int j=0;j<grid[i].size();j++) {
                    sum=0;
                    if(grid[i][j]==1) {
                        stack<pair<int,int>> s;
                        helper(v,d,vis,grid,s,i,j,m,n,sum);
                    } else v.push_back(sum);
                }
            }
            auto max_index = max_element(v.begin(),v.end())-v.begin();
            return v[max_index];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

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

相关阅读

相关 695. 岛屿的最大面积

695. 岛屿的最大面积给你一个大小为 m x n 的二进制矩阵 grid 。岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在

古城微笑少年丶/ 2024年03月31日 08:50/ 0 赞/ 59 阅读

相关 leetcode695. 岛屿的最大面积

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】][offer_

Love The Way You Lie/ 2024年03月26日 10:39/ 0 赞/ 56 阅读

相关 leetcode 695. Max Area of Island（岛屿的最大面积）

[https://leetcode.com/problems/max-area-of-island/][https_leetcode.com_problems_max-area

曾经终败给现在/ 2022年12月03日 09:55/ 0 赞/ 130 阅读

相关 Max Area of Island（C++岛屿的最大面积）

解题思路：（1）利用栈(stack)来进行深度遍历(dfs) class Solution { public: void

分手后的思念是犯贱/ 2022年11月06日 12:51/ 0 赞/ 174 阅读

相关 695. 岛屿的最大面积

> 给定一个包含了一些 0 和 1 的非空二维数组 grid 。 > > 一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者

灰太狼/ 2022年10月08日 05:44/ 0 赞/ 139 阅读

相关 Leetcode 695. 岛屿的最大面积

题目重述给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平

青旅半醒/ 2022年09月08日 12:55/ 0 赞/ 175 阅读

相关 leetcode 695. Max Area of Island 岛屿的最大面积 + 十分典型的深度优先遍历DFS

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representin

迈不过友情╰/ 2022年06月03日 08:39/ 0 赞/ 178 阅读

相关 leetcode 695. 岛屿的最大面积python

给定一个包含了一些 0 和 1的非空二维数组 `grid` , 一个岛屿是由四个方向 (水平或垂直) 的 `1` (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被

浅浅的花香味﹌/ 2022年05月13日 16:27/ 0 赞/ 228 阅读

相关岛屿的最大面积

1、题目描述给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的

àì夳堔傛蜴生んèń/ 2022年01月21日 08:51/ 0 赞/ 206 阅读

相关 695. 岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着

迷南。/ 2021年11月14日 13:08/ 0 赞/ 315 阅读