【DFS】695.岛屿的最大面积_最大岛屿面积dfspython-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/135663889

该博客围绕“岛屿的最大面积”问题展开，介绍使用深度优先搜索（DFS）方法求解。强调最简单的DFS必须掌握，还给出了Python和Java两种语言的实现方向。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

法1：DFS

最简单的DFS必须掌握！！！

Python

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        maxArea = 0
        m, n = len(grid), len(grid[0])
        visited = [[False]*n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and not visited[i][j]:
                    maxArea = max(maxArea, self.dfs(grid, i, j, visited))
        
        return maxArea
    
    def dfs(self, grid, i, j, visited):
        if (i < 0 or i >= len(grid) 
            or j < 0 or j >= len(grid[0])
            or grid[i][j] == 0 
            or visited[i][j]):
            return 0
        visited[i][j] = True

        return (1 + self.dfs(grid, i-1, j, visited) 
                    + self.dfs(grid, i+1, j, visited)
                    + self.dfs(grid, i, j-1, visited) 
                    + self.dfs(grid, i, j+1, visited))

Java

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, ans = 0;
        if (m == 0 || n == 0) {
            return ans;
        }
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    ans = Math.max(ans, dfs(grid, visited, i, j));
                }
            }
        }

        return ans;
    }

    public int dfs(int[][] grid, boolean[][] visited, int i, int j) {
        if (i >= 0 && i < grid.length 
                && j >= 0 && j < grid[0].length 
                && grid[i][j] == 1 
                && !visited[i][j]) {
            visited[i][j] = true;
            return 1 + dfs(grid, visited, i - 1, j) 
                    + dfs(grid, visited, i + 1, j)
                    + dfs(grid, visited, i, j - 1)
                    + dfs(grid, visited, i, j + 1);  
        }
        return 0;
    }
}