算法题/网格DFS：岛屿的周长

题目

给定一个row行，col列的二维网格，其中1表示陆地，0表示水。网格中的格子水平和垂直方向相连。整个网格被水完全包围，但其中恰好有一个岛屿。岛屿中没有湖，格子是边长为1的正方形。网格为长方形，且宽和高均不超过100.

示例1：

输入：grid=[
    ["0","1","0","0"],
    ["1","1","1","0"],
    ["0","1","0","0"],
    ["1","1","0","0"],
]
输出：16

示例2：

输入：grid=[[1]]
输出：4

示例3：

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

解答

Java

public int islandPerimeter(int[][] grid) {
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                // 题目限制只有一个岛屿，计算一个即可
                return dfs(grid, r, c);
            }
        }
    }
    return 0;
}

int dfs(int[][] grid, int r, int c) {
    // 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
    if (!inArea(grid, r, c)) {
        return 1;
    }
    // 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
    if (grid[r][c] == 0) {
        return 1;
    }
    // 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
    if (grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 2;
    return dfs(grid, r - 1, c)
        + dfs(grid, r + 1, c)
        + dfs(grid, r, c - 1)
        + dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

JavaScript

function islandPerimeter(grid) {
    for (let r = 0; r < grid.length; r++) {
        for (let c = 0; c < grid[0].length; c++) {
            if (grid[r][c] === 1) {
                // 题目限制只有一个岛屿，计算一个即可
                return dfs(grid, r, c);
            }
        }
    }
    return 0;
}

function dfs(grid, r, c) {
    // 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
    if (!inArea(grid, r, c)) {
        return 1;
    }
    // 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
    if (grid[r][c] === 0) {
        return 1;
    }
    // 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
    if (grid[r][c] !== 1) {
        return 0;
    }
    grid[r][c] = 2;
    return dfs(grid, r - 1, c)
        + dfs(grid, r + 1, c)
        + dfs(grid, r, c - 1)
        + dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
function inArea(grid, r, c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

Python

def islandPerimeter(grid):
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                # 题目限制只有一个岛屿，计算一个即可
                return dfs(grid, r, c)
    return 0

def dfs(grid, r, c):
    # 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
    if not inArea(grid, r, c):
        return 1
    # 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
    if grid[r][c] == 0:
        return 1
    # 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
    if grid[r][c] != 1:
        return 0
    grid[r][c] = 2
    return dfs(grid, r - 1, c) \
        + dfs(grid, r + 1, c) \
        + dfs(grid, r, c - 1) \
        + dfs(grid, r, c + 1)

# 判断坐标 (r, c) 是否在网格中
def inArea(grid, r, c):
    return 0 <= r < len(grid) and 0 <= c < len(grid[0])

Go

func islandPerimeter(grid [][]int) int {
    for r := 0; r < len(grid); r++ {
        for c := 0; c < len(grid[0]); c++ {
            if grid[r][c] == 1 {
                // 题目限制只有一个岛屿，计算一个即可
                return dfs(grid, r, c)
            }
        }
    }
    return 0
}

func dfs(grid [][]int, r int, c int) int {
    // 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
    if !inArea(grid, r, c) {
        return 1
    }
    // 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
    if grid[r][c] == 0 {
        return 1
    }
    // 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
    if grid[r][c] != 1 {
        return 0
    }
    grid[r][c] = 2
    return dfs(grid, r-1, c) +
        dfs(grid, r+1, c) +
        dfs(grid, r, c-1) +
        dfs(grid, r, c+1)
}

// 判断坐标 (r, c) 是否在网格中
func inArea(grid [][]int, r int, c int) bool {
    return r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0])
}