[C++知识库]c++实现八数码游戏

c++实现八数码游戏

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <utility>
#include <iomanip>
#include <unordered_set>
#include <time.h>
#include <conio.h>
//#define int long long

using namespace std;
const int N = 4e5 + 10;
bool book[N] = {0};
int mov[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
int step[N] = {0};

int jiecheng(int n)
{
    if (n == 0 || n == 1)
        return 1;
    int ans = 1;
    for (int i = 1; i <= n; i++)
    {
        ans *= i;
    }
    return ans;
}

int kangtuo(int arr[4][4])
{
    int ans = 0;
    int tp = 8;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            int cnt = 0;
            for (int k = 1; k <= 3; k++)
            {
                for (int p = 1; p <= 3; p++)
                {
                    if ((k - 1) * 3 + p > (i - 1) * 3 + j)
                    {
                        if (arr[i][j]>arr[k][p]) cnt++;
                    }
                }
            }
            ans+=cnt*jiecheng(9-(i-1)*3-j);
        }
    }
    return ans + 1;
}

struct node
{
    int temp_state[4][4];
    int temp_x, temp_y;
};

bool operator==(node a, node b)
{
    int cnt = 0;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            if (a.temp_state[i][j] != b.temp_state[i][j])
                return 0;
        }
    }
    return 1;
}

bool check(int x, int y)
{
    return x <= 3 && x >= 1 && y <= 3 && y >= 1;
}

void Print(node a, node b)
{
    for (int i = 1; i <= 12; i++)
        cout << " ";
    cout << "|"
         << " goal:" << endl;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            if (a.temp_state[i][j] == 9)
                cout << " "
                     << "   ";
            else
                cout << a.temp_state[i][j] << "   ";
        }
        cout << "|"
             << "       ";
        for (int j = 1; j <= 3; j++)
        {
            if (b.temp_state[i][j] == 9)
                cout << " "
                     << "   ";
            else
                cout << b.temp_state[i][j] << "   ";
        }
        cout << endl;
        for (int j = 1; j <= 12; j++)
            cout << " ";
        cout << "|";
        if (i < 3)
            cout << endl;
        else
        {
            for (int j = 1; j <= 20; j++)
                cout << " ";
            cout << "dis:" <<step[kangtuo(a.temp_state)]-1<<endl;
        }
    }
    for (int i = 1; i <= 45; i++)
        cout << "-";
    cout << endl;
}

void bfs(node prime)
{
    queue<node> pq;
    pq.push(prime);
    int kt_prim=kangtuo(prime.temp_state);
    step[kt_prim] = 1;
    book[kt_prim] = 1;
    while (!pq.empty())
    {
        node node_tp = pq.front();
        pq.pop();
        int x = node_tp.temp_x, y = node_tp.temp_y;
        int tp_num = kangtuo(node_tp.temp_state);
        for (int i = 0; i < 4; i++)
        {
            node node_tp1=node_tp;
            int tx = x + mov[i][0];
            int ty = y + mov[i][1];
            if (!check(tx, ty))
                continue;
            swap(node_tp1.temp_state[x][y], node_tp1.temp_state[tx][ty]);
            node_tp1.temp_x = tx;
            node_tp1.temp_y = ty;
            int ttp_num = kangtuo(node_tp1.temp_state);
            if (book[ttp_num] == 1)
                continue;
            step[ttp_num] = step[tp_num] + 1;
            pq.push(node_tp1);
            book[ttp_num] = 1;
        }
    }
}

node init()
{
    srand(time(0));
    int a = rand() % jiecheng(9);
    node node1;
    int tp_arr[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    while (a--)
    {
        next_permutation(tp_arr, tp_arr + 9);
    }
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            node1.temp_state[i][j] = tp_arr[(i - 1) * 3 + (j - 1)];
            if (node1.temp_state[i][j] == 9)
            {
                node1.temp_x = i;
                node1.temp_y = j;
            }
        }
    }
    return node1;
}

void update(node &a, char b)
{
    int x = a.temp_x, y = a.temp_y;
    if (b == 'w')
    {
        if (check(x - 1, y))
        {
            swap(a.temp_state[x][y], a.temp_state[x - 1][y]);
            a.temp_x--;
        }
    }
    else if (b == 's')
    {
        if (check(x + 1, y))
        {
            swap(a.temp_state[x][y], a.temp_state[x + 1][y]);
            a.temp_x++;
        }
    }
    else if (b == 'a')
    {
        if (check(x, y - 1))
        {
            swap(a.temp_state[x][y], a.temp_state[x][y - 1]);
            a.temp_y--;
        }
    }
    else if (b == 'd')
    {
        if (check(x, y + 1))
        {
            swap(a.temp_state[x][y], a.temp_state[x][y + 1]);
            a.temp_y++;
        }
    }
}

int main()
{
    memset(book, 0, sizeof book);
    memset(step, 0, sizeof step);
    node en = init();
    bfs(en);
    node start = init();
    while(en==start||step[kangtuo(start.temp_state)]==0)
    {
        start=init();
    }
    char op;
    Print(start, en);
    while (1)
    {
        op = getch();
        update(start, op);
        Print(start, en);
        if (start == en)
        {
            cout << "congratulations to you" << endl;
            break;
        }
    }
    return 0;
}