【BFS】八数码问题（c++基础算法）

���录

一.读题

二.在做题之前

1.康拓展开

2.DFS和BFS的区别

3.栈和队列的区别

三.做题

1.算法原理

2.算法实现

①队列

②康托展开

 ③标记

四.AC代码

---

一.读题

作为最经典的一道宽度优先搜索题，它的题面并不是很难懂。

【宽搜（难度：6）】8数码问题

题目描述

【题意】 

  

在3×3的棋盘上摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围上下左右相邻的棋子可以移到空格中。

现给出原始状态和目标状态，求实现从初始布局到目标布局的最少步骤（初始状态的步数为0）。

如下图，答案为5。 

  

 

【输入格式】

    第一个3*3的矩阵是原始状态；

    第二个3*3的矩阵是目标状态。

【输出格式】

    输出移动所用最少的步数。

【样例1输入】

2 8 3

1 6 4

7 0 5

1 2 3

8 0 4

7 6 5

【样例1输出】

5

 

【样例2输入】

2 8 3

1 6 4

7 0 5

0 1 2

3 4 5

8 7 6

【样例2输出】

17

很显然，这是要我们求出矩阵1通过白色方块的上下左右移动转化向矩阵2的最小步数。

---

二.在做题之前

在做题之前，我们先要弄懂3个问题。

1.康拓展开

在这道题中，我们要利用康托展开判断是否重复。在文前，蒟蒻已经写了一篇文章，不懂的可以去看一下：【宽搜必备】康托展开（从公式解析到代码实现）

那么，我们就可以写出：

int kt(int a[],int n){int s=1;for(int i=1;i