算法思想之广度优先搜索（BFS）及示例（亲子游戏）

广度优先搜索

广度优先算法，又称广度优先搜索算法，是最简便的图的算法之一，其特点是：在扫描数据空间时，每个点以最短路径生成广度优先生成树。广度优先搜索这种算法遍历整个图的所有节点并记录，直至找到所需结果为止，是一种盲目算法，但它还有一个非常重要的特性一最佳解，即当所有的边长相等，它就是最佳解，若在距离聚类算法中，应用广度优先搜索此特性去搜寻数据对象的同类，则可以有效地提高聚类速度。

此外，可以把网格单元作为点来处理，利用广度优先搜索某网格的直接网格邻居单元邻居和间接网格邻居单元，以类似于树的层次迅速遍历整个网格空间，对符合条件的所有找到的邻居合并，从而将显著网格单元进行连通并聚类。同时设置类门限，归类时做出正确判断，提高聚类精度。

主要过程

1. 将图中所有结点储存在队列中；
2. 从队列取出第一个结点，从此结点出发，访其未访问的所有邻接点，并将此结点从队列中删除；
3. 对所有邻接点重复步骤(2)，直至队列为空。

编号方案

广度优先搜索编号即分层编号，是按照节点。支路及分支线距离根节点的远近，将网络元件划分为不同层次。然后根据层次遍历树的访问顺序，来给各支路和节点编号。广度优先搜索方案分为基于支路分层法和分支线分层法

亲子游戏

• 题目描述

  宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。

  游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。

  请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。

  输入描述

  第一行输入为 N，N 表示二维矩阵的大小；

  之后 N 行，每行有 N 个值，表格矩阵每个位置的值，其中：

  • -3：妈妈
  • -2：宝宝
  • -1：障碍
  • ≥0：糖果数（0表示没有糖果，但是可以走）

  输出描述

  输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格

  备注：地图最大 50*50

  示例1

  输入：
  4
  3 2 1 -3
  1 -1 1 1
  1 1 -1 2
  -2 1 2 3
  输出：9
  说明：K小姐初始位置在 (0, 3),LYA 的位置在 (3, 0)。K小姐最短路径为 (0, 3) -> (1, 3) -> (2, 3) -> (3, 2) -> (3, 1) -> (3, 0),总共可以拿到 3 + 1 + 2 + 2 + 1 = 9 颗糖果
  

  示例2

  输入：
  4
  3 2 1 -3
  -1 -1 1 1
  1 1 -1 2
  -2 1 -1 3
  输出：-1
  

• 题解

  import java.util.*;
  public class Main {
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          while (sc.hasNext()) {
              int n = sc.nextInt();
              int[][] arr = new int[n][n];
              Node startNode = null, endNode = null;
              for (int i = 0; i < n; i++) {
                  for (int j = 0; j < n; j++) {
                      arr[i][j] = sc.nextInt();
                      if (arr[i][j] == -3) startNode = new Node(i, j, -3, null);
                      if (arr[i][j] == -2) endNode = new Node(i, j, -2, null);
                  }
              }
              System.out.println(bfs(arr, startNode, endNode));
          }
      }
      public static int bfs(int[][] arr, Node startNode, Node endNode) {
          int[][] addArr = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 左右上下移动
          boolean flag = false;
          int[][] visitedArr = new int[arr.length][arr.length];
          ArrayList<Node> retList = new ArrayList<>(); // 存储最短路径的终节点
          LinkedList<Node> currentList = new LinkedList<>(); // 存储某个时刻移动中的节点
          currentList.add(startNode);
          while (!currentList.isEmpty()) {
              if (flag) break; // 已到达终点，结束移动
              for (int i = 0; i < currentList.size(); i++) { // 模拟所有路线同时前进
                  Node currentNode = currentList.poll();
                  if (currentNode.x == endNode.x && currentNode.y == endNode.y) {
                      retList.add(currentNode);
                      flag = true;
                  }
                  visitedArr[currentNode.x][currentNode.y] = 1; // 访问过的节点设置为1
                  for (int[] add : addArr) { // 模拟一个路线同时向所有可以移动的方向尝试移动
                      int x = currentNode.x + add[0], y = currentNode.y + add[1];
                      if (x >= 0 && x < arr.length && y >= 0 && y < arr.length
                              && visitedArr[x][y] == 0 && arr[x][y] != -1)
                          // 正确路线：同时满足x合法，y合法，没访问过，不是障碍
                          currentList.offer(new Node(x, y, arr[x][y], currentNode));
                  }
              }
          }
          int max = -1;
          for (Node rootNode : retList) {
              int sum = 0;
              Node fatherNode = rootNode.father;
              while (fatherNode != null) {
                  if (fatherNode.v > 0) sum += fatherNode.v;
                  fatherNode = fatherNode.father;
              }
              max = Math.max(sum, max);
          }
          return max;
      }
      public static class Node{
          public int x, y, v;
          public Node father; // 指向前一个节点
          public Node(int x, int y, int v, Node father) {
              this.x = x; this.y = y; this.v = v; this.father = father;
          }
      }
  }