LeetCode 695 Max Area of Island

标签: 岛屿问题 LeetCode 发布于:2022-02-02 17:24:40 编辑于:2022-02-05 16:54:38 浏览量:380

题目分析

https://leetcode.com/problems/max-area-of-island/

深度优先搜索

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res = 0;
        for (int i=0; i<grid.size(); i++) {
            for (int j=0; j<grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    int cnt = 0;
                    travelIsland(i, j, grid, cnt);
                    res = max(res, cnt);
                }
            }
        }
        return res;
    }
    
    void travelIsland(int i, int j, vector<vector<int>>& grid, int& count) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()) return;
        if (grid[i][j] == 1) {
            grid[i][j] = 2; // mark as visited island
            count += 1;
            travelIsland(i+1, j, grid, count);
            travelIsland(i-1, j, grid, count);
            travelIsland(i, j+1, grid, count);
            travelIsland(i, j-1, grid, count);
        }
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/