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

  • 开发
  • 26

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 广度优先搜索

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:]
	}
}

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
}

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
}

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
}
阅读全部

相关推荐

  3. 代码随想录-图论

    2024-07-09 18:52:05       30 阅读

  5. 代码随想录：图论_01基础

    2024-07-09 18:52:05       24 阅读

  6. 代码随想录算法训练营Day 62| 图论 part02 | 695. 岛屿的最大面积、1020.飞地的数量、130.被围绕的区域

    2024-07-09 18:52:05       33 阅读

  8. 代码随想录（番外）图论2

    2024-07-09 18:52:05       32 阅读

  10. 代码随想录（番外）图论4

    2024-07-09 18:52:05       29 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-09 18:52:05       67 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-09 18:52:05       72 阅读

  9. 在Django里面运行非项目文件

    2024-07-09 18:52:05       58 阅读

  19. Python语言-面向对象

    2024-07-09 18:52:05       69 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-09 18:52:05       64 阅读

热门阅读

  4. 使用Spring Boot和Couchbase实现NoSQL数据库

    2024-07-09 18:52:05       31 阅读

  11. R语言学习笔记3-基本类型篇

    2024-07-09 18:52:05       27 阅读

  12. 【trition-server】pytorch 文档：使用 Triton 提供 Torch-TensorRT 模型

    2024-07-09 18:52:05       25 阅读

  14. pytorch通过 tensorboardX 调用 Tensorboard 进行可视化

    2024-07-09 18:52:05       25 阅读

  15. PHP框架详解 - symfony框架

    2024-07-09 18:52:05       29 阅读

  16. 【TORCH】查看dataloader里的数据，通过dataloader.dataset或enumerate

    2024-07-09 18:52:05       31 阅读

  18. PyTorch简介

    2024-07-09 18:52:05       32 阅读

  19. Emacs有什么优点，用Emacs写程序真的比IDE更方便吗？

    2024-07-09 18:52:05       30 阅读

  23. Apache AGE vs Neo4j

    2024-07-09 18:52:05       27 阅读

  26. 数据库基础

    2024-07-09 18:52:05       27 阅读

  27. centos7系统如何使用GPT分区

    2024-07-09 18:52:05       30 阅读