Flood Fille 模型

所有边权重相同的图，可以在线性时间内，查找到所有的连通块。

求最小的…
bfs基于迭代实现，因此不会曝栈，但是大概率可能会超时。

例题：
1. 池塘计数
2. 山峰和山谷
3. 城堡问题

会遍历所有的点，bfs

代码样例 池塘计数

package flood_fill

import "fmt"

var (
    M int
    N int
)

// FloodFill1097 池塘计数
func FloodFill1097() {
    _, _ = fmt.Scanln(&N, &M)

    arr := make([]string, N)
    for i := 0; i < N; i++ {
        _, _ = fmt.Scan(&arr[i])
    }

    cnt := 0

    // 是否访问过该节点 state 的缩写
    st := make([][]bool, N)
    for i := 0; i < N; i++ {
        st[i] = make([]bool, M)
    }

    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            // 若该节点有水，且未访问过，从该节点开始宽搜
            if arr[i][j] == 'W' && !st[i][j] {
                bfs(&arr, i, j, &st)
                cnt++
            }
        }
    }

    fmt.Println("count:", cnt)
}

func bfs(arr *[]string, rl int, rr int, st *[][]bool) {
    type node []int
    var queue []node
    var l, r int
    queue = append(queue, node{rl, rr})
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        l = cur[0]
        r = cur[1]
        // 遍历当前节点的周围节点, 八连通
        for i := -1; i <= 1; i++ {
            for j := -1; j <= 1; j++ {
                // 当前位置
                if i == 0 && j == 0 {
                    continue
                }
                // 超出边界
                if l+i < 0 || l+i >= N || r+j < 0 || r+j >= M {
                    continue
                }
                // 若是土地或已经访问过
                if (*arr)[l+i][r+j] == '.' || (*st)[l+i][r+j] {
                    continue
                }
                (*st)[l+i][r+j] = true
                // 进队
                queue = append(queue, node{l + i, r + j})
            }
        }
    }
}

单元最短路径问题

从指定点触发，通过bfs的性质，找到达到目的点的最短路径或最短距离

• 最短路径可以通过指定path[i,j]，存储上一跳的位置
• 最短距离可以通过dist[i,j]，存储上一条的距离，或者说次数

例题：
- 迷宫问题，求最短路径
- 武士风度的牛，求最短距离
- 抓住那头牛

代码样例，忽略风格

// 午时风度的牛
package min_path

import "fmt"

type node []int

// Knight 武士风度的牛
func Knight() {
    var c, r int

    _, _ = fmt.Scanln(&c, &r)

    // 处理输入
    arr := make([]string, r)
    for i := 0; i < r; i++ {
        _, _ = fmt.Scanln(&arr[i])
    }

    // 查找起始点
    // 起点终点
    var start node

    for i := 0; i < r; i++ {
        for idx, elem := range arr[i] {
            if elem == 'K' {
                start = node{i, idx}
                break
            }
        }
    }

    distance := dfsKnight(arr, start, c, r)

    fmt.Println(distance)
}

func dfsKnight(arr []string, start node, c int, r int) int {
    // dx dy
    dx := []int{-1, 1, -2, 2, -2, 2, -1, 1}
    dy := []int{-2, -2, -1, -1, 1, 1, 2, 2}

    // 需要求至少要跳多少次
    dist := make([][]int, r)
    for i := 0; i < r; i++ {
        dist[i] = make([]int, c)
        for j := 0; j < c; j++ {
            dist[i][j] = -1
        }
    }
    // 队列
    var queue []node
    queue = append(queue, start)
    dist[start[0]][start[1]] = 0

    // 从start节点开始bfs
    for len(queue) > 0 {
        // 出队
        current := queue[0]
        queue = queue[1:]
        x := current[0]
        y := current[1]

        for i := 0; i < len(dx); i++ {
            tx := x + dx[i]
            ty := y + dy[i]
            // 越界
            if tx < 0 || tx >= r || ty < 0 || ty >= c {
                continue
            }
            // 障碍物
            if arr[tx][ty] == '*' {
                continue
            }
            // 若已经访问过
            if dist[tx][ty] >= 0 {
                continue
            }
            dist[tx][ty] = dist[x][y] + 1
            queue = append(queue, node{tx, ty})
            // 若是终点
            if arr[tx][ty] == 'H' {
                // print(dist)
                return dist[tx][ty]
            }
        }
    }
    return -1
}

func print(dist [][]int) {
    for _, row := range dist {
        for _, val := range row {
            fmt.Printf("\t%d", val)
        }
        fmt.Println()
    }
    fmt.Println("------------------------------------")
}

// 城堡问题
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class T1076 {
    private class Node {
        int x;

        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    int[] dx = {-1, 0, 1, 0};

    int[] dy = {0, 1, 0, -1};

    public void Labyrinth() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scanner.nextInt();
            }
        }

        // 前一个节点
        Node[][] previous = new Node[n][n];

        bfs(arr, previous);

        List<Node> ans = new LinkedList<>();
        Node pre = new Node(n - 1, n - 1);
        ans.add(pre);

        do {
            pre = previous[pre.x][pre.y];
            ans.add(pre);
        } while (pre.x != 0 || pre.y != 0);

        for (int i = ans.size() - 1; i >= 0; i--) {
            System.out.println(ans.get(i).x + " " + ans.get(i).y);
        }
    }

    // 从左上，到右下，假设必定有解
    private void bfs(int[][] arr, Node[][] previous) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0));
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            int x = cur.x;
            int y = cur.y;

            for (int i = 0; i < 4; i++) {
                int tx = x + dx[i];
                int ty = y + dy[i];
                // 数组越界
                if (tx < 0 || ty < 0 || tx >= arr.length || ty >= arr[0].length) {
                    continue;
                }
                // 墙壁或者已经访问过
                if (arr[tx][ty] == 1 || previous[tx][ty] != null) {
                    continue;
                }
                // visit
                previous[tx][ty] = cur;

                // 遍历到右下角
                if (tx == arr.length - 1 && ty == arr[0].length - 1) {
                    return;
                }

                queue.offer(new Node(tx, ty));
            }
        }
    }

    public static void main(String[] args) {
        new T1076().Labyrinth();
    }
}