八数码问题（bfs广度优先搜索）

最近在学bfs，觉得这个题不错，自己没做出来，去网上搜了一下，又结合了我自己的想法，ac了；

这个看起来用dfs比较好做，但是会超时好像，所以肯定用bfs了。

问题描述：

　　在九宫格里放在1到8共8个数字还有一个是x，与x相邻的数字可以移动到x的位置，问给定的状态最少需要几步能到达目标状态：

　　1 2 3

       4 5 6

       7 8 x

输入：

　　输入一个初始状态；

输出：

　　到达目标状态所需要的最少步数；

样例：

　　输入：

　　　　1 2 3

　　　　x 4 6

　　　　7 5 8

　　输出：

　　　　19

思路：

　　首先，可以根据输入的初始状态直接判断此题是否有解，无解的情况直接输出-1就ok了；

　　具体方法是：将输入的九个数存到一个一维数组，假设f（1）为数字1在数组位置中在1前面比1小的数，

　　f（2）为数字2在数组位置中，在2前面比2小的数，.........，直到f（8），将f（1）+f（2）.....到f(8)的值相加，

　　如果得到的数是偶数则有解，奇数则无解。

　　然后，将每个状态的九宫格替换成一个整数表示，例如样例 123046758，x替换成0，然后用map，来存储状态是否被　　　　　访问过，这样只需遍历0所在位置可以移动的方向，如果没有出界的话，求出移动后的九宫格状态，压入队列中，直到目标解，返回最少步数。具体实现请看代码。

ac代码：

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 #include
  7 #include
  8 #define inf 0x3f3f3f3f
  9 using namespace std;
 10 const int N = 10000 + 10;
 11 int dx[] = { 1,-1,0,0 };
 12 int dy[] = { 0,0,1,-1 };
 13 
 14 int a[5][5], d[10];
 15 map<int, int>vis;  //存储九宫格状态是否被访问过
 16 map<int, int>step; //存储到达此状态所需的最少步数
 17 int px, py, lx, ly;
 18 
 19 bool check(int u, int v) {        //将九宫格换成二维数组形式，并检查移动后是否出界
 20     int r = u, x, y;
 21     for (int i = 3; i >= 1; i--) {
 22         for (int j = 3; j >= 1; j--) {
 23             a[i][j] = r % 10;
 24             r /= 10;
 25             if (a[i][j] == 0) {
 26                 lx = i, ly = j;
 27                 px = i + dx[v], py = j + dy[v];
 28                 //cout << x << " " << y;
 29             }
 30             //cout << a[i][j] << " ";
 31         }
 32         //cout << "\n";
 33     }
 34     //cout << "\n";
 35     
 36     if (px >= 1 && px <= 3 && py >= 1 && py <= 3) {
 37         return true;
 38     }
 39     else return false;
 40 }
 41 
 42 int move_to(int ax, int ay, int bx, int by) {   //求解移动后的九宫格状态
 43     //cout << "...";
 44     a[ax][ay] = a[bx][by];
 45     a[bx][by] = 0;
 46     int val = 0;
 47     for (int i = 1; i <= 3; i++) {
 48         for (int j = 1; j <= 3; j++) {
 49             val = val * 10 + a[i][j];
 50         }
 51     }
 52     return val;
 53 }
 54 
 55 int bfs(int k) {        //bfs求最少步数
 56     queue<int>q;
 57     q.push(k);
 58     vis[k] = 1;
 59     step[k] = 0;
 60     while (!q.empty()) {
 61         int t = q.front();
 62         //cout << t << "\n";
 63         q.pop();
 64         int r = t, x = 0, y = 0;
 65         if (t == 123456780) {    //如果到达返回最少步数
 66             return step[t];
 67         }
 68         for (int i = 0; i < 4; i++) {
 69             //int px = x + dx[i];
 70             //int py = y + dy[i];
 71             //cout << px << " " << py << "\n";
 72             //cout << "...";
 73             if (check(t, i)) {
 74                 int pos_now = move_to(lx, ly, px, py);
 75                 //cout << pos_now << "ppp" << "\n";
 76                 if (!vis[pos_now]) {
 77                     /*for (int i = 1; i <= 3; i++) {
 78                         for (int j = 1; j <= 3; j++) {
 79                             cout << a[i][j] << " ";
 80                         }
 81                         cout << "\n";
 82                     }*/
 83                     //cout << "\n";
 84                     vis[pos_now] = 1;
 85                     step[pos_now] = step[t] + 1;
 86                     q.push(pos_now);
 87                 }
 88             }
 89         }
 90     }
 91     return 0;
 92 }
 93 
 94 int main() {
 95 
 96     int x = 0, cut = 1;
 97     for (int i = 1; i <= 3; i++) {
 98         for (int j = 1; j <= 3; j++) {
 99             char ch;
100             cin >> ch;
101             if (ch == 'x') ch = '0';
102             a[i][j] = ch - '0';
103             x = x * 10 + a[i][j];
104             d[cut++] = a[i][j];
105             //cout << a[i][j] << "\n";
106         }
107     }
108     //求九宫格是否有解
109     int rem = 0;
110     for (int i = 1; i <= 9; i++) {
111         for (int j = 1; j < i; j++) {
112             if (d[j] == 0) continue;
113             if (d[i] > d[j]) rem++;
114         }
115     }
116     //cout << x << "\n";
117     if (rem % 2) {
118         cout << -1 << "\n";
119     }
120     else {
121         int ans = bfs(x);
122         if (ans) cout << ans << "\n";
123     }
124     
125     return 0;
126 }
BFS

相关

BZOJ 1195 [HNOI2006]最短母串 (Trie图+状压+bfs最短路)

关于DFS和BFS

[ACM] BFS & 双端BFS & A* & 双边BFS

P1443 马的遍历（BFS广度优先搜索）

洛谷P1141 01迷宫 （BFS连通块问题）

算法-03 | 深度优先DFS| 广度优先BFS | 剪枝优化

[bzoj] 2657 ZJOI2012 旅游 || bfs

图的存储、遍历（BFS、DFS)

计蒜客 一维坐标的移动 bfs

leetcode542. 01 矩阵（dp 多源bfs）

01-BFS

五三想休息，今天还学习，图解二叉树的层序遍历BFS（广度优先）模板，附面试题题解

标签