算法题/网格DFS：岛屿的最大连通面积

题目

给定一个二维网格，其中有一些岛屿，求岛屿的最大连通面积。

示例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,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

示例2：

输入：grid=[
    [0,0,0,0,0,0,0,0,0,0,0,0,0]
]
输出：0

解答

Java

public int maxAreaOfIsland(int[][] grid) {
    int res = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                int a = area(grid, r, c);
                res = Math.max(res, a);
            }
        }
    }
    return res;
}

int area(int[][] grid, int r, int c) {
    if (!inArea(grid, r, c)) {
        return 0;
    }
    if (grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 2;
  
    return 1 
        + area(grid, r - 1, c)
        + area(grid, r + 1, c)
        + area(grid, r, c - 1)
        + area(grid, r, c + 1);
}

boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

JavaScript

function maxAreaOfIsland(grid) {
    let res = 0;
    for (let r = 0; r < grid.length; r++) {
        for (let c = 0; c < grid[0].length; c++) {
            if (grid[r][c] === 1) {
                let a = area(grid, r, c);
                res = Math.max(res, a);
            }
        }
    }
    return res;
}

function area(grid, r, c) {
    if (!inArea(grid, r, c)) {
        return 0;
    }
    if (grid[r][c] !== 1) {
        return 0;
    }
    grid[r][c] = 2;

    return 1 +
        area(grid, r - 1, c) +
        area(grid, r + 1, c) +
        area(grid, r, c - 1) +
        area(grid, r, c + 1);
}

function inArea(grid, r, c) {
    return (
        0 <= r && r < grid.length &&
        0 <= c && c < grid[0].length
    );
}

Python

def maxAreaOfIsland(grid):
    res = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                a = area(grid, r, c)
                res = max(res, a)
    return res

def area(grid, r, c):
    if not inArea(grid, r, c):
        return 0
    if grid[r][c] != 1:
        return 0
    grid[r][c] = 2

    return 1 + 
           area(grid, r - 1, c) + 
           area(grid, r + 1, c) + 
           area(grid, r, c - 1) + 
           area(grid, r, c + 1)

def inArea(grid, r, c):
    return 0 <= r < len(grid) and 0 <= c < len(grid[0])

Go

func maxAreaOfIsland(grid [][]int) int {
	res := 0
	for r := 0; r < len(grid); r++ {
		for c := 0; c < len(grid[0]); c++ {
			if grid[r][c] == 1 {
				a := area(grid, r, c)
				res = max(res, a)
			}
		}
	}
	return res
}

func area(grid [][]int, r, c int) int {
	if !inArea(grid, r, c) {
		return 0
	}
	if grid[r][c] != 1 {
		return 0
	}
	grid[r][c] = 2

	return 1 +
		area(grid, r-1, c) +
		area(grid, r+1, c) +
		area(grid, r, c-1) +
		area(grid, r, c+1)
}

func inArea(grid [][]int, r, c int) bool {
	return r >= 0 && r < len(grid) &&
		c >= 0 && c < len(grid[0])
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}