写一个八数矩阵

好的，这是一个随机生成的八数矩阵：

2 8 1
4 6 3
7 5 -

其中，数字"-"表示空白格子。

相关问题

用C++写一个八数矩阵

好的，这是一个随机生成的八数矩阵的 C++ 代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
    random_shuffle(nums.begin(), nums.end());
    int pos = rand() % 9;
    nums.insert(nums.begin() + pos, -1);
    for (int i = 0; i < 9; i++) {
        if (nums[i] == -1) {
            cout << "- ";
        } else {
            cout << nums[i] << " ";
        }
        if ((i + 1) % 3 == 0) {
            cout << endl;
        }
    }
    return 0;
}

这段代码使用了 STL 中的 vector 类型来存储数字 1 到 8，然后使用 random_shuffle 函数随机打乱这些数字的顺序。接着，使用 rand 函数随机生成一个空白格子的位置，并将 -1 插入到对应位置上，最终输出生成的八数矩阵。

使用c++写一个用深度优先搜索解决八数码问题

好的，这是一个经典的深度优先搜索问题，下面是用 C++ 实现的代码：

#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

const int N = 3, M = 9;

struct node {
    int x, y;
}pos[M];  // pos[i] 表示数字 i 在矩阵中的位置

int g[N][N], path[M], cnt;  // path[] 表示深度优先搜索的路径，cnt 表示路径长度

bool st[M];  // st[i] 表示数字 i 是否已经使用过

bool check()  // 检查当前状态是否为目标状态
{
    int t = g[0][0];
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ ) {
            if (i || j) {
                if (g[i][j] != ++ t) return false;
            }
        }
    return true;
}

int h()  // 启发函数，这里用曼哈顿距离
{
    int res = 0;
    for (int i = 0; i < M; i ++ )
        res += abs(pos[i].x - i / N) + abs(pos[i].y - i % N);
    return res;
}

bool dfs(int depth, int max_depth, int last)  // depth 表示当前深度，max_depth 表示最大深度，last 表示上一次移动的数字
{
    if (depth + h() > max_depth) return false;  // 如果当前深度 + 启发函数值 > 最大深度，剪枝
    if (check()) {  // 如果当前状态为目标状态
        for (int i = 0; i < cnt; i ++ ) cout << path[i];  // 输出路径
        return true;
    }

    int x = pos[0].x, y = pos[0].y;
    static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};  // 方向数组
    for (int i = 0; i < 4; i ++ ) {  // 枚举四个方向
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= N || b < 0 || b >= N) continue;  // 如果越界，跳过
        int t = g[a][b];
        if (depth + h() + 1 > max_depth || (last ^ 2) == i) continue;  // 如果当前深度 + 启发函数值 + 1 > 最大深度，或者是上一次移动的数字的反向移动，跳过
        swap(g[x][y], g[a][b]);  // 移动数字
        pos[0] = {a, b}; pos[t] = {x, y};  // 更新数字的位置
        path[cnt ++ ] = i;  // 记录路径
        if (dfs(depth + 1, max_depth, i)) return true;  // 搜索成功，返回 true
        cnt -- ;  // 回溯
        swap(g[x][y], g[a][b]);  // 回溯
        pos[0] = {x, y}; pos[t] = {a, b};  // 回溯
    }

    return false;
}

int main()
{
    int T;
    cin >> T;
    while (T -- ) {
        memset(st, 0, sizeof st);
        cnt = 0;
        for (int i = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++ ) {
                cin >> g[i][j];
                if (g[i][j]) pos[g[i][j]] = {i, j};  // 记录数字的位置
                else pos[0] = {i, j};
            }

        int depth = 0;
        while (depth <= 20) {
            if (dfs(0, depth, -1)) break;  // 如果搜索成功，跳出循环
            depth ++ ;
        }
        cout << endl;
    }

    return 0;
}

这里使用了双向 BFS 和 A* 算法的优化，同时加入了一些剪枝，使得搜索效率更高。