463.岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中： grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：

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

示例 3：

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

提示：

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] 为 0 或 1

解法一：DFS

var pairs = []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}

func islandPerimeter(grid [][]int) int {
    res := 0
    var dfs func([][]int, int, int)

    dfs = func(grid [][]int, x, y int) {
        if x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) || grid[x][y] == 0 {
            res++
            return
        }
        if grid[x][y] == 2 {
            return
        }
        grid[x][y] = 2
        for _, pair := range pairs {
            dfs(grid, x+pair.x, y+pair.y)
        }
        return
    }
    for i, row := range grid {
        for j, val := range row {
            if val == 1 {
                dfs(grid, i, j)
            }
        }
    }
    return res
}

或者是改成这样

var pairs = []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}

func islandPerimeter(grid [][]int) int {
    for i, row := range grid {
        for j, val := range row {
            if val == 1 {
                return dfs(grid, i, j)
            }
        }
    }
    return -1
}

func dfs(grid [][]int, x, y int) int {
    if x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) || grid[x][y] == 0 {
        return 1
    }
    if grid[x][y] == 2 {
        return 0
    }
    grid[x][y] = 2
    temp := 0
    for _, pair := range pairs {
        temp += dfs(grid, x+pair.x, y+pair.y)
    }
    return temp
}

解法二： 归纳总结

判断当前岛下面和右边是否存在，如果存在就 -2

func islandPerimeter(grid [][]int) int {
    res := 0
    m := len(grid)
    n := len(grid[0])
    for i, row := range grid {
        for j, val := range row {
            if val == 1 {
                res += 4
                if i < m-1 && grid[i+1][j] == 1 {
                    res -= 2
                }
                if j < n-1 && grid[i][j+1] == 1 {
                    res -= 2
                }
            }
        }
    }
    return res
}

解法三： 暴力法

判断当前节点上下左右是否是边界或水域。

var pairs = []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}


func islandPerimeter(grid [][]int) int {
    res := 0
    m := len(grid)
    n := len(grid[0])
    for i, row := range grid {
        for j, val := range row {
            if val == 1 {
                for _, pair := range pairs {
                    if x, y := i + pair.x, j+pair.y; x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) || grid[x][y] == 0 {
                        res++
                    }
            }
        }
    }
    return res
}