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

1.岛屿数量

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

1.1 深度优先搜索

package mainimport "fmt"var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}func main() {var M, N intfmt.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])}}// 开始遍历searesult := 0for 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] = truedfs(newX, newY, sea, visited)}}
}

1.2 广度优先搜索

package mainimport "fmt"var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}func main() {var M, N intfmt.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])}}// 开始遍历searesult := 0for 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] = truefor 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 mainimport "fmt"var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}func main() {var M, N intfmt.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])}}// 开始遍历searesult := 0for 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] = truearea := 0for 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 mainimport "fmt"var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}func main() {var M, N intfmt.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)}}// 开始遍历searesult := 0for 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] = truearea := 0for 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 mainimport "fmt"var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}func main() {var M, N intfmt.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)}}// 开始遍历visitedfor 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] = truearea := 0for len(queue) != 0 {pos := queue[0]queue = queue[1:]area += 1for 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
}