062宽度优先遍历及其扩展

bfs的特点是逐层扩散，从源头点到目标点扩散了几层，最短路就是多少
bfs可以使用的特征是 任意两个节点之间的相互距离相同(无向图)
bfs开始时，可以是单源也可以是多个源头
bfs频繁使用队列，形式可以是单点弹出或者整层弹出
bfs进行时，进入队列的节点要标记状态，防止同一个节点重复进出队列
bfs进行时，可能会包含剪纸策略的设计
bfs难点在于节点如何找到路，路的展开，剪枝设计

// 地图分析
// 你现在手里有一份大小为 n x n 的 网格 grid
// 上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。
// 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的
// 并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
// (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
// 测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/
class Solution {
    public static int MAXN = 101;
    public static int MAXM = 101;
    public static int[][] queue = new int[MAXN * MAXM][2];
    public static int l, r;
    public static boolean[][] visited = new boolean[MAXN][MAXM];
    
    // dx 数组表示行坐标的变化，dy 数组表示列坐标的变化
    public static int[] dx = new int[]{-1, 1, 0, 0}; // 上、下、左、右
    public static int[] dy = new int[]{0, 0, -1, 1}; // 上、下、左、右

    public int maxDistance(int[][] grid) {
        l = r = 0;
        int n = grid.length;
        int m = grid[0].length;
        int seas = 0;
        
        // 初始化 visited 数组和队列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    visited[i][j] = true;
                    queue[r][0] = i;
                    queue[r++][1] = j;
                } else {
                    visited[i][j] = false;
                    seas++;
                }
            }
        }
        
        // 特殊情况处理：只有陆地或只有海洋
        if (seas == 0 || seas == n * m) {
            return -1;
        }

        int level = 0;
        
        // BFS 核心循环
        while (l < r) {
            int size = r - l;
            for (int k = 0, x, y, nx, ny; k < size; k++) {
                x = queue[l][0];
                y = queue[l++][1];
                
                // 遍历四个方向
                for (int i = 0; i < 4; i++) {
                    nx = x + dx[i];
                    ny = y + dy[i];
                    
                    // 检查新坐标是否合法且未被访问
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue[r][0] = nx;
                        queue[r++][1] = ny;
                    }
                }
            }
            level++;
        }
        
        return level - 1;
    }
}

691贴纸拼词

class Solution {


// 贴纸拼词
// 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
// 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们
// 如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
// 返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1
// 注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的
// 并且 target 被选择为两个随机单词的连接。
// 测试链接 : https://leetcode.cn/problems/stickers-to-spell-word/
    public static int MAXN = 401;

    public static String[] queue = new String[MAXN];

    public static int l, r;

    // 下标0 -> a
    // 下标1 -> b
    // 下标2 -> c
    // ...
    // 下标25 -> z
    public static ArrayList<ArrayList<String>> graph = new ArrayList<>();

    static {
        for (int i = 0; i < 26; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public static HashSet<String> visited = new HashSet<>();
    public static int minStickers(String[] stickers, String target) {
        for (int i = 0; i < 26; i++) {
            graph.get(i).clear();
        }
        visited.clear();
        for (String str : stickers) {
            str = sort(str);
            for (int i = 0; i < str.length(); i++) {
                if (i == 0 || str.charAt(i) != str.charAt(i - 1)) {
                    graph.get(str.charAt(i) - 'a').add(str);
                }
            }
        }
        target = sort(target);
        visited.add(target);
        l = r = 0;
        queue[r++] = target;
        int level = 1;
        // 使用队列的形式是整层弹出
        while (l < r) {
            int size = r - l;
            for (int i = 0; i < size; i++) {
                String cur = queue[l++];
                for (String s : graph.get(cur.charAt(0) - 'a')) {
                    String next = next(cur, s);
                    if (next.equals("")) {
                        return level;
                    } else if (!visited.contains(next)) {
                        visited.add(next);
                        queue[r++] = next;
                    }
                }
            }
            level++;
        }
        return -1;
    }

    public static String sort(String str) {
        char[] s = str.toCharArray();
        Arrays.sort(s);
        return String.valueOf(s);
    }

    public static String next(String t, String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0, j = 0; i < t.length();) {
            if (j == s.length()) {
                builder.append(t.charAt(i++));
            } else {
                if (t.charAt(i) < s.charAt(j)) {
                    builder.append(t.charAt(i++));
                } else if (t.charAt(i) > s.charAt(j)) {
                    j++;
                } else {
                    i++;
                    j++;
                }
            }
        }
        return builder.toString();
    }

}