代码随想录

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

# 106. 岛屿的周长

卡码网题目链接（ACM模式） (opens new window)

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。

你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿，假设组成岛屿的陆地边长都为 1，请计算岛屿的周长。岛屿内部没有水域。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的周长。

输入示例

5 5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
1
2
3
4
5
6

输出示例

14

提示信息

岛屿的周长为 14。

数据范围：

1 <= M, N <= 50。

# 思路

岛屿问题最容易让人想到BFS或者DFS，但本题确实还用不上。

为了避免大家惯性思维，所以给大家安排了这道题目。

# 解法一：

遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。

如果该陆地上下左右的空格是有水域，则说明是一条边，如图：

陆地的右边空格是水域，则说明找到一条边。

如果该陆地上下左右的空格出界了，则说明是一条边，如图：

该陆地的下边空格出界了，则说明找到一条边。

C++代码如下：（详细注释）

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    int direction[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                for (int k = 0; k < 4; k++) {       // 上下左右四个方向
                    int x = i + direction[k][0];
                    int y = j + direction[k][1];    // 计算周边坐标x,y
                    if (x < 0                       // x在边界上
                            || x >= grid.size()     // x在边界上
                            || y < 0                // y在边界上
                            || y >= grid[0].size()  // y在边界上
                            || grid[x][y] == 0) {   // x,y位置是水域
                        result++;
                    }
                }
            }
        }
    }
    cout << result << endl;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 解法二：

计算出总的岛屿数量，总的变数为：岛屿数量 * 4

因为有一对相邻两个陆地，边的总数就要减2，如图红线部分，有两个陆地相邻，总边数就要减2

那么只需要在计算出相邻岛屿的数量就可以了，相邻岛屿数量为cover。

结果 result = 岛屿数量 * 4 - cover * 2;

C++代码如下：（详细注释）

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    int sum = 0;    // 陆地数量
    int cover = 0;  // 相邻数量
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                sum++; // 统计总的陆地数量
                // 统计上边相邻陆地
                if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;
                // 统计左边相邻陆地
                if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;
                // 为什么没统计下边和右边？ 因为避免重复计算
            }
        }
    }

    cout << sum * 4 - cover * 2 << endl;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 其他语言版本

# Java

import java.util.*;

public class Main {
    // 每次遍历到1，探索其周围4个方向，并记录周长，最终合计
    // 声明全局变量，dirs表示4个方向
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    // 统计每单个1的周长
    static int count;
    
    // 探索其周围4个方向，并记录周长
    public static void helper(int[][] grid, int x, int y) {
        for (int[] dir : dirs) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            
            // 遇到边界或者水，周长加一
            if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length
                || grid[nx][ny] == 0) {
                count++;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 接收输入
        int M = sc.nextInt();
        int N = sc.nextInt();

        int[][] grid = new int[M][N];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        int result = 0; // 总周长
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) {
                    count = 0;
                    helper(grid, i, j);
                    // 更新总周长
                    result += count;
                }
            }
        }
        
        // 打印结果
        System.out.println(result);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# Python


def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    # 读取 n 和 m
    n = int(data[0])
    m = int(data[1])
    
    # 初始化 grid
    grid = []
    index = 2
    for i in range(n):
        grid.append([int(data[index + j]) for j in range(m)])
        index += m
    
    sum_land = 0    # 陆地数量
    cover = 0       # 相邻数量

    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                sum_land += 1
                # 统计上边相邻陆地
                if i - 1 >= 0 and grid[i - 1][j] == 1:
                    cover += 1
                # 统计左边相邻陆地
                if j - 1 >= 0 and grid[i][j - 1] == 1:
                    cover += 1
                # 不统计下边和右边，避免重复计算
    
    result = sum_land * 4 - cover * 2
    print(result)

if __name__ == "__main__":
    main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# Go


package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	line := scanner.Text()
	
	n, m := parseInput(line)

	// 初始化 grid
	grid := make([][]int, n)
	for i := range grid {
		grid[i] = make([]int, m)
	}

	// 读入 grid 数据
	for i := 0; i < n; i++ {
		scanner.Scan()
		line := scanner.Text()
		values := parseLine(line, m)
		for j := 0; j < m; j++ {
			grid[i][j] = values[j]
		}
	}

	sum := 0   // 陆地数量
	cover := 0 // 相邻数量

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				sum++ // 统计总的陆地数量

				// 统计上边相邻陆地
				if i-1 >= 0 && grid[i-1][j] == 1 {
					cover++
				}
				// 统计左边相邻陆地
				if j-1 >= 0 && grid[i][j-1] == 1 {
					cover++
				}
				// 为什么没统计下边和右边？ 因为避免重复计算
			}
		}
	}

	fmt.Println(sum*4 - cover*2)
}

// parseInput 解析 n 和 m
func parseInput(line string) (int, int) {
	parts := strings.Split(line, " ")
	n, _ := strconv.Atoi(parts[0])
	m, _ := strconv.Atoi(parts[1])
	return n, m
}

// parseLine 解析一行中的多个值
func parseLine(line string, count int) []int {
	parts := strings.Split(line, " ")
	values := make([]int, count)
	for i := 0; i < count; i++ {
		values[i], _ = strconv.Atoi(parts[i])
	}
	return values
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

# Rust

# Javascript

# TypeScript

# PhP

# Swift

# Scala

# C#

# Dart

# C

上次更新：: 9/14/2024, 11:52:04 AM

← 15. 并查集理论基础 →

@2021-2024 代码随想录 版权所有 粤ICP备19156078号