【模板】广度优先搜索（bfs）

• 使用

1、最少、最优、优先，最先等字眼，区别于动态规划。 每个状态间相互独立。 只要空间，时间允许，动态规划的算法可以转化为 bfs算法。

2、描述中，有递归的规律。比如由一个状态，能到转换为其他状态。

•  要素

1、用队列来实现

2、元素数据结构定义。

3、初始元素定义

4、一个元素继续生成其他元素方法

5、符合条件退出队列方法

6、去重。相同元素不能重复进队。

• 模板 （完整代码见 【力扣】773. 滑动谜题）

// 元素数据结构定义

class Data {
		int[][] mat;
		int val;
		int len;

		public Data(int[][] mat, int len) {
			this.mat = mat;
			this.val = toHash(this.mat);
			this.len = len;
		}

	}
           

//  增加其他元素

public void addData(Data data) { // 产生下一个。

		int[][] mat = data.mat;
		int m = mat.length;
		int n = mat[0].length;

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (mat[i][j] == 0) {
					for (int k = 0; k < 4; k++) {
						int[][] nm = change(mat, i, j, k);
						if (nm == null) {
							continue;
						}
						Data d = new Data(nm, data.len + 1);

						if (sets.contains(d.val)) {
							continue;
						}
						sets.add(d.val);
						datas.add(d);
					}
					return;
				}

			}
		}
	}
           

// 队列 （ 包括增加初始元素、 判断退出方法）

Queue<Data> datas = new LinkedList<>();
	Set<Integer> sets = new HashSet<>();

	public int slidingPuzzle(int[][] board) {

		Data data = new Data(board, 0);
		datas.offer(data);
		sets.add(data.val);
		while (!datas.isEmpty()) {
			data = datas.poll();
			if (data.val == 54321) {
				return data.len;
			}
			this.addData(data);

		}
		return -1;
	}