题目描述

初始状态的步数就算1，哈哈

输入：第一个33的矩阵是原始状态，第二个33的矩阵是目标状态。
输出：移动所用最少的步数

Input

2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5

Output

6

分析：首先要理解题意。数字0代表空格，空格周围的棋子可以移到空格中,通过一定的步骤由初始状态变到到目标状态。使用广度优先算法，问题的关键在于如何记录状态。

思路一：用一个3×3的二维数组记录状态。通过记录上一步的状态使得每一步都不会直接往回走，简化运算。

#include <cstdio>
#include <queue>
using namespace std;

struct node {
    int x, y;
    int step;
    int M[3][3];
    int oldX, oldY;
} Node;
int X[4] = {0, 0, 1, -1}; //增量数组
int Y[4] = {1, -1, 0, 0};
int start[3][3], final[3][3];

bool judge(int x, int y) { //判断是否越界
    if (x < 0 || x >= 3 || y < 0 || y >= 3)
        return false;
    return true;
}
bool same(int a[3][3]) { //判断是否和目标一致
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[i][j] != final[i][j])
                return false;
        }
    }
    return true;
}
int BFS(int x, int y) {
    queue<node> Q;
    Node.x = x, Node.y = y, Node.step = 1;
    Node.oldX = x, Node.oldY = y;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            Node.M[i][j] = start[i][j];
        }
    }
    Q.push(Node);
    while (!Q.empty()) {
        node top = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++) {
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            if (judge(newX, newY) && (newX != top.oldX || newY != top.oldY)) { //与上一步不重合
                Node.x = newX, Node.y = newY;
                Node.step = top.step + 1;
                Node.oldX = top.x, Node.oldY = top.y; //记录上一步
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        Node.M[i][j] = top.M[i][j];
                    }
                }
                //非0数与0交换位置
                Node.M[top.x][top.y] = Node.M[newX][newY];
                Node.M[newX][newY] = 0;
                if (same(Node.M)) {
                    return Node.step;
                }
                Q.push(Node);
            }
        }
    }
    return -1;
}
int main() {
    int x0, y0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &start[i][j]);
            if (start[i][j] == 0) {
                x0 = i, y0 = j;
            }
        }
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &final[i][j]);
        }
    }
    printf("%d\n", BFS(x0, y0));
    return 0;
}

思路二：利用一个9位的整数保存状态的数字序列，通过map建立映射。如题中初试状态对应的9位整数为283164705，目标状态对应的9位整数为123804765。

```cpp
#include <cstdio>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
struct node {
    int a[3][3];
    int x0, y0; //记录0的位置
    int step; //记录步数
};
map<int, bool> M; //建立映射
int arr_to_num(int t[3][3]) {
    int num = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) { num = num * 10 + t[i][j]; }
    }
    return num;
}
bool change(node &t, int n) { //使用引用以实现交换
    int x = t.x0, y = t.y0;
    if (n == 0 && x > 0) { //上
        swap(t.a[x][y], t.a[x - 1][y]);
        t.x0 -= 1;
    } else if (n == 1 && x < 2) { //下
        swap(t.a[x][y], t.a[x + 1][y]);
        t.x0 += 1;
    } else if (n == 2 && y > 0) { //左
        swap(t.a[x][y], t.a[x][y - 1]);
        t.y0 -= 1;
    } else if (n == 3 && y < 2) { //右
        swap(t.a[x][y], t.a[x][y + 1]);
        t.y0 += 1;
    } else {
        return false;
    }
    return true;
}
int main() {
    node start, end;
    for (int i = 0; i < 3; i++) { //初始状态
        for (int j = 0; j < 3; j++) {
            scanf("%d", &start.a[i][j]);
            if (start.a[i][j] == 0) {
                start.x0 = i;
                start.y0 = j;
            }
        }
    }
    for (int i = 0; i < 3; i++) { //目标状态
        for (int j = 0; j < 3; j++) { scanf("%d", &end.a[i][j]); }
    }
    queue<node> Q;
    start.step = 1, end.step = 0;
    Q.push(start);
    M[arr_to_num(start.a)] = 1;
    int flag = 0;
    while (!Q.empty()) {
        node top = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++) { // 0，1，2，3分别代表0的上下左右
            node temp = top;
            if (change(temp, i)) { //如果可以交换则交换
                if (M[arr_to_num(temp.a)] == 0) { //该状态未出现过
                    M[arr_to_num(temp.a)] = 1;
                    temp.step++;
                    if (arr_to_num(temp.a)
                        == arr_to_num(end.a)) { //与最终结点的值相同
                        end.step = temp.step;
                        flag = 1;
                        break;
                    }
                    Q.push(temp);
                }
            }
        }
        if (flag) break;
    }
    printf("%d", end.step);
    return 0;
}

思路三：参考了大神使用的A*+BFS+map方法。

#include <cstdio>
#include <map>
#include <queue>

using namespace std;
char goal[10];
int start, termination;
struct node {
    int step, cost, num, pos;
    node(int n, int s, int p) { //构造函数
        num = n;
        step = s;
        pos = p;
        compute();
    }
    friend bool operator<(const node &n1, const node &n2) { // cost低的优先级高
        return n1.cost > n2.cost;
    }
    void compute() { //计算cost
        int c = 0;
        char temp[10];
        sprintf(temp, "%09d", num);
        for (int i = 0; i < 9; i++) {
            if (temp[i] != goal[i]) c++;
        }
        cost = step + c;
    }
};
// 0出现在0->8的位置后该和哪些位置交换
//-1表示不能交换，4个数字分别表示上下左右换的数字序号
int director[9][4] = {{-1, -1, 3, 1}, {-1, 0, 4, 2}, {-1, 1, 5, -1},
                      {0, -1, 6, 4},  {1, 3, 7, 5},  {2, 4, 8, -1},
                      {3, -1, -1, 7}, {4, 6, -1, 8}, {5, 7, -1, -1}};
void swap(char str[], int a, int b) { //交换字符数组第a个和第b个元素
    char temp = str[a];
    str[a] = str[b];
    str[b] = temp;
}
bool judge(char a[], char b[]) { //判断8数码问题是否有解
    int r1 = 0, r2 = 0;
    for (int i = 0; i < 9; i++) {
        if (a[i] == '0') continue;
        for (int j = 0; j < i; j++) {
            if (a[j] == '0') continue;
            if (a[j] > a[i]) r1++;
        }
    }
    for (int i = 0; i < 9; i++) {
        if (b[i] == '0') continue;
        for (int j = 0; j < i; j++) {
            if (b[j] == '0') continue;
            if (b[j] > b[i]) r2++;
        }
    }
    if (r1 % 2 == r2 % 2)
        return true;
    else
        return false;
}
priority_queue<node> p;
map<int, bool> mp;
int change(int num, int pos) {
    char temp[10];
    int temp1;
    node s(num, 1, pos);
    p.push(s);
    mp[num] = true;
    while (!p.empty()) {
        s = p.top();
        p.pop();
        sprintf(temp, "%09d", s.num);
        for (int i = 0; i < 4; i++) { //上下左右
            if (director[s.pos][i] != -1) { //可以换
                swap(temp, s.pos, director[s.pos][i]);
                sscanf(temp, "%d", &temp1);
                if (s.num == termination) return s.step; //和目标一致
                if (mp.count(temp1) == 0) {
                    node r(temp1, s.step + 1, director[s.pos][i]);
                    p.push(r);
                    mp[temp1] = true;
                }
                swap(temp, s.pos, director[s.pos][i]);
            }
        }
    }
}

int main() {
    int n, pos;
    char temp[10];
    while (~scanf("%d", &n)) {
        start = n;
        for (int i = 0; i < 8; i++) {
            scanf("%d", &n);
            start = start * 10 + n;
        }
        sprintf(temp, "%09d", start);
        for (int i = 0; i < 9; i++)
            if (temp[i] == '0') pos = i; //找到0的位置
        termination = 0;
        for (int i = 0; i < 9; i++) {
            scanf("%d", &n);
            termination = termination * 10 + n;
        }
        sprintf(goal, "%09d", termination);
        if (judge(temp, goal)) { //有解
            int count = 0;
            count = change(start, pos);
            printf("%d\n", count);
        } else {
            printf("-1\n");
        }
    }
    return 0;
}

参考链接：
思路一
思路二
思路三
7种方法求解八数码问题