论坛 › 物联网 › 代码随想录 day52 第十一章 图论part03

河曲智叟 发表于 2024-12-24 10:26:14

代码随想录 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

package main

import (
    "fmt"
)

var count int
var dir = int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}} // 四个方向

func bfs(grid [][]int, x, y int) {
    queue := []int{{x, y}}
    grid = 0 // 只要加入队列，立刻标记
    count++
   
    for len(queue) > 0 {
      cur := queue
      queue = queue
      curx, cury := cur, cur
      
      for i := 0; i < 4; i++ {
            nextx := curx + dir
            nexty := cury + dir
            
            if nextx < 0 || nextx >= len(grid) || nexty < 0 || nexty >= len(grid) {
                continue // 越界了，直接跳过
            }
            
            if grid == 1 {
                queue = append(queue, int{nextx, nexty})
                count++
                grid = 0 // 只要加入队列立刻标记
            }
      }
    }
}

func main() {
    var n, m int
    fmt.Scan(&n, &m)
   
    grid := make([][]int, n)
    for i := range grid {
      grid = make([]int, m)
    }
   
    for i := 0; i < n; i++ {
      for j := 0; j < m; j++ {
            fmt.Scan(&grid)
      }
    }
   
    // 从左侧边，和右侧边向中间遍历
    for i := 0; i < n; i++ {
      if grid == 1 {
            bfs(grid, i, 0)
      }
      if grid == 1 {
            bfs(grid, i, m-1)
      }
    }
   
    // 从上边和下边向中间遍历
    for j := 0; j < m; j++ {
      if grid == 1 {
            bfs(grid, 0, j)
      }
      if grid == 1 {
            bfs(grid, n-1, j)
      }
    }
   
    // 清空之前的计数
    count = 0
   
    // 遍历所有位置
    for i := 0; i < n; i++ {
      for j := 0; j < m; j++ {
            if grid == 1 {
                bfs(grid, i, j)
            }
      }
    }
   
    fmt.Println(count)
}



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企服之家，中国第一个企服评测及商务社交产业平台。

查看完整版本: 代码随想录 day52 第十一章 图论part03