day53 第十一章：图论part04

---
title: 代码随想录 day53 第11章 图论part04
date: 2024-12-22 23:48:48
modificationDate: 2024 十二月 22日 星期日 23:48:48
categories: 
    - carl
tags: []
sticky: []
hide: false
category_bar: true
---

# **第十一章：图论part04**

经过上面的练习，大家可能会感觉 广搜不过如此，都刷出自信了，本题让大家初步感受一下，广搜难不在广搜本身，而是如何应用广搜。

https://www.programmercarl.com/kamacoder/0110.%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%8E%A5%E9%BE%99.html

```go
// ladderLength 实现 BFS 查找最短路径长度
func ladderLength(beginWord, endWord string, wordList []string) int {
    wordSet := make(map[string]struct{})
    for _, word := range wordList {
        wordSet[word] = struct{}{}
    }

    if _, exists := wordSet[endWord]; !exists {
        return 0
    }

    queue := []string{beginWord}
    visitMap := make(map[string]int)
    visitMap[beginWord] = 1

    for len(queue) > 0 {
        currentWord := queue[0]
        queue = queue[1:]
        path := visitMap[currentWord]

        for i := 0; i < len(currentWord); i++ {
            chars := []rune(currentWord)
            for ch := 'a'; ch <= 'z'; ch++ {
                chars[i] = ch
                newWord := string(chars)

                if newWord == endWord {
                    return path + 1
                }

                if _, exists := wordSet[newWord]; exists {
                    if _, visited := visitMap[newWord]; !visited {
                        visitMap[newWord] = path + 1
                        queue = append(queue, newWord)
                    }
                }
            }
        }
    }

    return 0
}

```

深搜有细节，同样是深搜两种写法的区别，以及什么时候需要回溯操作呢？

https://www.programmercarl.com/kamacoder/0105.%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%AE%8C%E5%85%A8%E5%8F%AF%E8%BE%BE%E6%80%A7.html

```python
import collections

path = set()  # 纪录 BFS 所经过之节点

def bfs(root, graph):
    global path
    
    que = collections.deque([root])
    while que:
        cur = que.popleft()
        path.add(cur)
        
        for nei in graph[cur]:
            que.append(nei)
        graph[cur] = []
    return

def main():
    N, K = map(int, input().strip().split())
    graph = collections.defaultdict(list)
    for _ in range(K):
        src, dest = map(int, input().strip().split())
        graph[src].append(dest)
    
    bfs(1, graph)
    if path == {i for i in range(1, N + 1)}:
        return 1
    return -1
        

if __name__ == "__main__":
    print(main())
```
  

简单题，避免大家惯性思维，建议大家先独立做题。

https://www.programmercarl.com/kamacoder/0106.%E5%B2%9B%E5%B1%BF%E7%9A%84%E5%91%A8%E9%95%BF.html

```python

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    # 读取 n 和 m
    n = int(data[0])
    m = int(data[1])
    
    # 初始化 grid
    grid = []
    index = 2
    for i in range(n):
        grid.append([int(data[index + j]) for j in range(m)])
        index += m
    
    sum_land = 0    # 陆地数量
    cover = 0       # 相邻数量

    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                sum_land += 1
                # 统计上边相邻陆地
                if i - 1 >= 0 and grid[i - 1][j] == 1:
                    cover += 1
                # 统计左边相邻陆地
                if j - 1 >= 0 and grid[i][j - 1] == 1:
                    cover += 1
                # 不统计下边和右边，避免重复计算
    
    result = sum_land * 4 - cover * 2
    print(result)

if __name__ == "__main__":
    main()

```