【代码随想录——图论——岛屿问题】_代码随想录官网

1.岛屿数量

https://kamacoder.com/problempage.php?pid=1171

1.1 深度优先搜索

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
	var M, N int
	fmt.Scanln(&N, &M)
	sea := make([][]int, N)
	visited := make([][]bool, N)
	for i := 0; i < N; i++ {
		sea[i] = make([]int, M)
		visited[i] = make([]bool, M)
	}

	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			fmt.Scan(&sea[i][j])
		}
	}
	// 开始遍历sea
	result := 0
	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			if sea[i][j] == 1 && !visited[i][j] {
				dfs(i, j, &sea, &visited)
				//bfs(i, j, &sea, &visited)
				result += 1
			}
		}
	}

	fmt.Println(result)
}

func dfs(x, y int, sea *[][]int, visited *[][]bool) {
	for i := 0; i < 4; i++ {
		newX := x + direction[i][0]
		newY := y + direction[i][1]
		if newX < 0 || newX >= len(*sea) || newY < 0 || newY >= len((*sea)[0]) {
			continue
		}
		if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
			(*visited)[newX][newY] = true
			dfs(newX, newY, sea, visited)
		}
	}
}
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

1.2 广度优先搜索

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
	var M, N int
	fmt.Scanln(&N, &M)
	sea := make([][]int, N)
	visited := make([][]bool, N)
	for i := 0; i < N; i++ {
		sea[i] = make([]int, M)
		visited[i] = make([]bool, M)
	}

	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			fmt.Scan(&sea[i][j])
		}
	}
	// 开始遍历sea
	result := 0
	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			if sea[i][j] == 1 && !visited[i][j] {
				bfs(i, j, &sea, &visited)
				result += 1
			}
		}
	}

	fmt.Println(result)
}

func bfs(i, j int, sea *[][]int, visited *[][]bool) {
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{i, j})
	(*visited)[i][j] = true
	for len(queue) != 0 {
		pos := queue[0]
		for i := 0; i < 4; i++ {
			newX := pos[0] + direction[i][0]
			newY := pos[1] + direction[i][1]
			if newX < 0 || newX >= len(*sea) || newY < 0 || newY >= len((*sea)[0]) {
				continue
			}
			if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
				queue = append(queue, [2]int{newX, newY})
				(*visited)[newX][newY] = true
			}
		}
		queue = queue[1:]
	}
}
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

2.岛屿的最大面积

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
	var M, N int
	fmt.Scanln(&N, &M)
	sea := make([][]int, N)
	visited := make([][]bool, N)
	for i := 0; i < N; i++ {
		sea[i] = make([]int, M)
		visited[i] = make([]bool, M)
	}

	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			fmt.Scan(&sea[i][j])
		}
	}
	// 开始遍历sea
	result := 0
	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			if sea[i][j] == 1 && !visited[i][j] {
				area := bfs(i, j, &sea, &visited)
				if area>result{
				    result = area
				}
			}
		}
	}

	fmt.Println(result)
}

func bfs(i, j int, sea *[][]int, visited *[][]bool) int {
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{i, j})
	(*visited)[i][j] = true
	area := 0
	for len(queue) != 0 {
		pos := queue[0]
		for i := 0; i < 4; i++ {
			newX := pos[0] + direction[i][0]
			newY := pos[1] + direction[i][1]
			if newX < 0 || newX >= len(*sea) || newY < 0 || newY >= len((*sea)[0]) {
				continue
			}
			if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
				queue = append(queue, [2]int{newX, newY})
				(*visited)[newX][newY] = true
			}
		}
		queue = queue[1:]
		area += 1
	}
	return area
}
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

3.孤岛的总面积

思路：很简单，只需要优先遍历一下四周的所有点即可。

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
	var M, N int
	fmt.Scanln(&N, &M)
	sea := make([][]int, N)
	visited := make([][]bool, N)
	for i := 0; i < N; i++ {
		sea[i] = make([]int, M)
		visited[i] = make([]bool, M)
	}

	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			fmt.Scan(&sea[i][j])
		}
	}
	//优先遍历陆地边缘
	for i := 0; i < N; i++ {
		if sea[i][0] == 1 && !visited[i][0] {
			bfs(i, 0, &sea, &visited)
		}
	}
	for i := 0; i < N; i++ {
		if sea[i][N-1] == 1 && !visited[i][N-1] {
			bfs(i, N-1, &sea, &visited)
		}
	}
	
	for i := 0; i < M; i++ {
		if sea[0][i] == 1 && !visited[0][i] {
			bfs(0, i, &sea, &visited)
		}
	}
	for i := 0; i < M; i++ {
		if sea[N-1][i] == 1 && !visited[N-1][i] {
			bfs(N-1, i, &sea, &visited)
		}
	}
	// 开始遍历sea
	result := 0
	for i := 1; i < N-1; i++ {
		for j := 1; j < M-1; j++ {
			if sea[i][j] == 1 && !visited[i][j] {
				area := bfs(i, j, &sea, &visited)
				result += area
			}
		}
	}

	fmt.Println(result)
}

func bfs(i, j int, sea *[][]int, visited *[][]bool) int {
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{i, j})
	(*visited)[i][j] = true
	area := 0
	for len(queue) != 0 {
		pos := queue[0]
		for i := 0; i < 4; i++ {
			newX := pos[0] + direction[i][0]
			newY := pos[1] + direction[i][1]
			if newX < 0 || newX >= len(*sea) || newY < 0 || newY >= len((*sea)[0]) {
				continue
			}
			if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
				queue = append(queue, [2]int{newX, newY})
				(*visited)[newX][newY] = true
			}
		}
		queue = queue[1:]
		area += 1
	}
	return area
}
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
78
79
80

4.沉没孤岛

思路：遍历完四周之后输出visited数组即可。

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
    var M, N int
    fmt.Scanln(&N, &M)
    sea := make([][]int, N)
    visited := make([][]bool, N)
    for i := 0; i < N; i++ {
        sea[i] = make([]int, M)
        visited[i] = make([]bool, M)
    }

    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            fmt.Scan(&sea[i][j])
        }
    }
    
    // 优先遍历陆地边缘
    for i := 0; i < N; i++ {
        if sea[i][0] == 1 && !visited[i][0] {
            bfs(i, 0, N, M, &sea, &visited)
        }
        if sea[i][M-1] == 1 && !visited[i][M-1] {
            bfs(i, M-1, N, M, &sea, &visited)
        }
    }
    
    for i := 0; i < M; i++ {
        if sea[0][i] == 1 && !visited[0][i] {
            bfs(0, i, N, M, &sea, &visited)
        }
        if sea[N-1][i] == 1 && !visited[N-1][i] {
            bfs(N-1, i, N, M, &sea, &visited)
        }
    }
    
    // 开始遍历visited
    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            if visited[i][j] {
                fmt.Print(1)
            } else {
                fmt.Print(0)
            }
            fmt.Print(" ")
        }
        fmt.Println()
    }
}

func bfs(i, j, N, M int, sea *[][]int, visited *[][]bool) int {
    queue := make([][2]int, 0)
    queue = append(queue, [2]int{i, j})
    (*visited)[i][j] = true
    area := 0
    for len(queue) != 0 {
        pos := queue[0]
        queue = queue[1:]
        area += 1
        for i := 0; i < 4; i++ {
            newX := pos[0] + direction[i][0]
            newY := pos[1] + direction[i][1]
            if newX < 0 || newX >= N || newY < 0 || newY >= M {
                continue
            }
            if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
                queue = append(queue, [2]int{newX, newY})
                (*visited)[newX][newY] = true
            }
        }
    }
    return area
}
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
78