代码随想录 day52 第十一章 图论part03

---

title: 代码随想录 day52 第十一章 图论part03
date: 2024-12-23 01:35:07
modificationDate: 2024 十二月 23日 星期一 01:35:07
categories:
- carl
tags: []
sticky: []
hide: false
category_bar: true

第十一章：图论part03

101.  孤岛的总面积

底子标题 可以本身尝试做一做 。
https://www.programmercarl.com/kamacoder/0101.%E5%AD%A4%E5%B2%9B%E7%9A%84%E6%80%BB%E9%9D%A2%E7%A7%AF.html

2. package main
4. import (
5.     "fmt"
6. )
8. var count int
9. var dir = [4][2]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}} // 四个方向
11. func bfs(grid [][]int, x, y int) {
12.     queue := [][2]int{{x, y}}
13.     grid[x][y] = 0 // 只要加入队列，立刻标记
14.     count++
15.    
16.     for len(queue) > 0 {
17.         cur := queue[0]
18.         queue = queue[1:]
19.         curx, cury := cur[0], cur[1]
20.         
21.         for i := 0; i < 4; i++ {
22.             nextx := curx + dir[i][0]
23.             nexty := cury + dir[i][1]
24.             
25.             if nextx < 0 || nextx >= len(grid) || nexty < 0 || nexty >= len(grid[0]) {
26.                 continue // 越界了，直接跳过
27.             }
28.             
29.             if grid[nextx][nexty] == 1 {
30.                 queue = append(queue, [2]int{nextx, nexty})
31.                 count++
32.                 grid[nextx][nexty] = 0 // 只要加入队列立刻标记
33.             }
34.         }
35.     }
36. }
38. func main() {
39.     var n, m int
40.     fmt.Scan(&n, &m)
41.    
42.     grid := make([][]int, n)
43.     for i := range grid {
44.         grid[i] = make([]int, m)
45.     }
46.    
47.     for i := 0; i < n; i++ {
48.         for j := 0; j < m; j++ {
49.             fmt.Scan(&grid[i][j])
50.         }
51.     }
52.    
53.     // 从左侧边，和右侧边向中间遍历
54.     for i := 0; i < n; i++ {
55.         if grid[i][0] == 1 {
56.             bfs(grid, i, 0)
57.         }
58.         if grid[i][m-1] == 1 {
59.             bfs(grid, i, m-1)
60.         }
61.     }
62.    
63.     // 从上边和下边向中间遍历
64.     for j := 0; j < m; j++ {
65.         if grid[0][j] == 1 {
66.             bfs(grid, 0, j)
67.         }
68.         if grid[n-1][j] == 1 {
69.             bfs(grid, n-1, j)
70.         }
71.     }
72.    
73.     // 清空之前的计数
74.     count = 0
75.    
76.     // 遍历所有位置
77.     for i := 0; i < n; i++ {
78.         for j := 0; j < m; j++ {
79.             if grid[i][j] == 1 {
80.                 bfs(grid, i, j)
81.             }
82.         }
83.     }
84.    
85.     fmt.Println(count)
86. }

复制代码

102.  沉没孤岛

和上一题差不多，尝试本身做做
https://www.programmercarl.com/kamacoder/0102.%E6%B2%89%E6%B2%A1%E5%AD%A4%E5%B2%9B.html
103.  水流题目

需要点优化思路，发起先本身读题，相处一个解题方法，有时间就本身写代码，没时间就直接看题解，优化方式 会让你 耳目一新。
https://www.programmercarl.com/kamacoder/0103.%E6%B0%B4%E6%B5%81%E9%97%AE%E9%A2%98.html
104.建造最大岛屿

同样优化思路也会让你耳目一新，本身想比力难想出来。
https://www.programmercarl.com/kamacoder/0104.%E5%BB%BA%E9%80%A0%E6%9C%80%E5%A4%A7%E5%B2%9B%E5%B1%BF.html

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。