463. 岛屿的周长
题目描述
输入 row x col 的网格 grid，1 代表陆地，0 代表水。每个格子是边长为 1 的正方形，只有上下左右相邻才算连通。
网格外围全是水。网格里恰好有一座岛，即一片连通的陆地，且岛内部没有被陆地围住的水域。
返回这座岛的周长，也就是陆地与水（含网格外部）之间分界边的总条数。
示例 1
输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] 输出：16
解释：岛由 7 个陆地格组成，与水相邻的边共 16 条。
示例 2
输入：grid = [[1]] 输出：4
解释：单个陆地格四条边都挨水。
示例 3
输入：grid = [[1,0]] 输出：4
解释：陆地格右边是水，其余三边是网格外部，共 4 条。
数据范围
row == grid.lengthcol == grid[i].length1 <= row, col <= 100grid[i][j]只会是0或1。
解题思路：迭代计数
每块陆地自带 4 条边。两块陆地相邻时，它们中间那条边两边都不算周长，要减去 2。扫描时只看上方和左边的邻居，每对相邻就恰好处理一次。
为什么正确
扫完前 k 个格子后，per 等于这些格子中陆地组成的图形的周长。
复杂度分析
时间 O(mn)，空间 O(1)。
易错点
共用边要减 2 而不是 1；如果四个方向都检查，就只能减 1，否则会重复减。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
per = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
per += 4
if i > 0 and grid[i - 1][j] == 1:
per -= 2
if j > 0 and grid[i][j - 1] == 1:
per -= 2
return perclass Solution {
public int islandPerimeter(int[][] grid) {
int m = grid.length, n = grid[0].length;
int per = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
per += 4;
if (i > 0 && grid[i - 1][j] == 1) {
per -= 2;
}
if (j > 0 && grid[i][j - 1] == 1) {
per -= 2;
}
}
}
}
return per;
}
}class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int per = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
per += 4;
if (i > 0 && grid[i - 1][j] == 1) {
per -= 2;
}
if (j > 0 && grid[i][j - 1] == 1) {
per -= 2;
}
}
}
}
return per;
}
};func islandPerimeter(grid [][]int) int {
m, n := len(grid), len(grid[0])
per := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
per += 4
if i > 0 && grid[i-1][j] == 1 {
per -= 2
}
if j > 0 && grid[i][j-1] == 1 {
per -= 2
}
}
}
}
return per
}var islandPerimeter = function(grid) {
const m = grid.length, n = grid[0].length;
let per = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
per += 4;
if (i > 0 && grid[i - 1][j] === 1) {
per -= 2;
}
if (j > 0 && grid[i][j - 1] === 1) {
per -= 2;
}
}
}
}
return per;
};function islandPerimeter(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
let per = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
per += 4;
if (i > 0 && grid[i - 1][j] === 1) {
per -= 2;
}
if (j > 0 && grid[i][j - 1] === 1) {
per -= 2;
}
}
}
}
return per;
}其他解法
迭代计数逐格统计相邻情况，最直接；DFS 把“周长”理解为“走出岛屿的次数”，更能体现图搜索思想。
解法 2：深度优先搜索 时间 O(mn)，空间 O(mn)
从任意一块陆地出发做 DFS，访问过的格子标记为 2。每当从陆地走到网格外或水域，就说明跨过了一条边界边，返回 1；走到已访问的陆地返回 0。所有返回值相加就是周长。
是岛屿类题目的通用模板，便于推广到多个岛屿等变形。需要递归栈和修改原网格，比直接计数更绕。
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def dfs(i, j):
# 从陆地走到边界外或水域，说明跨过了一条边
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
return 1
if grid[i][j] == 2:
return 0
grid[i][j] = 2
return dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
return dfs(i, j)
return 0class Solution {
private int m, n;
private int dfs(int[][] grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) return 1;
if (grid[i][j] == 2) return 0;
grid[i][j] = 2;
return dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
}
public int islandPerimeter(int[][] grid) {
m = grid.length;
n = grid[0].length;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) return dfs(grid, i, j);
return 0;
}
}class Solution {
public:
int m, n;
int dfs(vector<vector<int>>& grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) return 1;
if (grid[i][j] == 2) return 0;
grid[i][j] = 2;
return dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
}
int islandPerimeter(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) return dfs(grid, i, j);
return 0;
}
};func islandPerimeter(grid [][]int) int {
m, n := len(grid), len(grid[0])
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 {
return 1
}
if grid[i][j] == 2 {
return 0
}
grid[i][j] = 2
return dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
return dfs(i, j)
}
}
}
return 0
}var islandPerimeter = function(grid) {
const m = grid.length, n = grid[0].length;
const dfs = (i, j) => {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === 0) return 1;
if (grid[i][j] === 2) return 0;
grid[i][j] = 2;
return dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1);
};
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) return dfs(i, j);
return 0;
};function islandPerimeter(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
const dfs = (i: number, j: number): number => {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === 0) return 1;
if (grid[i][j] === 2) return 0;
grid[i][j] = 2;
return dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1);
};
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) return dfs(i, j);
return 0;
}