BFS

BFS和DFS比较： https://leetcode-cn.com/problems/open-the-lock/solution/wo-xie-liao-yi-tao-bfs-suan-fa-kuang-jia-jian-dao-/

1. BFS - 广度优先搜索

广度优先搜索（BFS）是一种遍历或搜索数据结构（如树或图）的算法。

我们可以使用 BFS 在树中执行层序遍历。

我们也可以使用 BFS 遍历图。例如，我们可以使用 BFS 找到从起始结点到目标结点的路径，特别是最短路径。

我们可以在更抽象的情景中使用 BFS 遍历所有可能的状态。在这种情况下，我们可以把状态看作是图中的结点，而以合法的过渡路径作为图中的边。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/k89rs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

BFS模板

public int BFS(Node node, Node target){
    LinkedList queue = new LinkedList();
    int step = 0; // 表示root到当前节点的步数
    //初始化, 添加root节点
    queue.add(node);

    while(!queue.isEmpty()) {
        step += 1;
        //找出当前queue中的节点数进行遍历
        int size = queue.size();
        for(int i = 0; i < size; i++) {
            Node curNode = queue.pollFirst();
            if(curNode == target){
                return step;
            }
            for(Node next : curNode.adj()) {
                queue.add(next);
            }
        }

    }
    return -1;
}

有时，确保我们永远不会访问一个结点两次。很重要。否则，我们可能陷入无限循环。如果是这样，我们可以在上面的代码中添加一个哈希集来解决这个问题。

public int BFS(Node node, Node target){
    LinkedList queue = new LinkedList();
    Set used = new HashSet<>();
    int step = 0; // 表示root到当前节点的步数
    //初始化, 添加root节点
    queue.add(node);
    used.add(node);
    while(!queue.isEmpty()) {
        step += 1;
        //找出当前queue中的节点数进行遍历
        int size = queue.size();
        for(int i = 0; i < size; i++) {
            Node curNode = queue.pollFirst();
            if(curNode == target){
                return step;
            }
            for(Node next : curNode.adj()) {
　　　　　　　　　 if(!used.contains(next){
                　　queue.add(next);
                　　used.add(next);
　　　　　　　　　　}
            }
        }

    }
    return -1;
}

 1. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：

输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/kbcqv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路：遍历grid数组，当发现1的时候，岛屿数量加1。压入队列，设置当前值为0. 同时用广度优先查找相邻元素是1的压入队列并设置当前值为0。直到相连没有1为止。

方法1：
public class SquareNum {
    public int numSquares(int n) {
        List squareNums = new ArrayList<>();
        for(int i = 1; i * i <= n; i++) {
            squareNums.add(i * i);
        }

        LinkedList queue = new LinkedList<>();
        queue.add(n);
        int level = 0;

        while(!queue.isEmpty()) {
            level++;
            int size = queue.size();

            for(int i = 0; i < size; i++) {
                int num = queue.poll();
                for(int squareNum : squareNums) {
                    if(num - squareNum > 0) {
                        queue.add(num - squareNum);
                    } else if (num == squareNum) {
                        return level;
                    } else{
                        break;
                    }
                }
            }
        }

        return level;
    }
}


方法2：此题类似兑换零钱。可以用动态规划解

1654. 到家的最少跳跃次数
有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。

跳蚤跳跃的规则如下：

它可以 往前 跳恰好 a 个位置（即往右跳）。
它可以 往后 跳恰好 b 个位置（即往左跳）。
它不能 连续 往后跳 2 次。
它不能跳到任何 forbidden 数组中的位置。
跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。

给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。

 

示例 1：

输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
输出：3
解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。
示例 2：

输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
输出：-1
示例 3：

输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
输出：2
解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。


class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        LinkedList<int[]> queue = new LinkedList<>();
        HashSet visited = new HashSet<>();
        for(int num : forbidden) {
            visited.add(num);
        }

        queue.add(new int[]{0,1});
        visited.add(0);


        int count = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();

            for(int i = 0; i < size; i++) {
                int[] step = queue.poll();

                if(step[0] == x) {
                    return count;
                }

                if(step[1] == 1 && step[0] - b > 0 && !visited.contains(step[0] - b)) {
                    queue.offer(new int[]{step[0] - b, -1});
                    visited.add(step[0] - b);
                }

                if(step[0] + a < 6000 && !visited.contains(step[0] + a)) {
                    queue.offer(new int[]{step[0]  + a, 1});
                    visited.add(step[0] + a);
                }
            }
            count++;
        }

        return -1;

    }
}