蓝桥杯九宫重排（bfs+用set去重）

题目连接

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<queue> 
#include<cmath>
#include<set>
#include<cstring>
using namespace std;
char s[4][4], e[4][4];
char  a[10];
struct point {
    int x, y;
    char status[4][4];
    int cnt = 0;
    point() {
    };
    point(int x, int y, char s[4][4] , int cnt) {
        this->x = x; this->y = y;
        for (int i = 0; i<3; i++)
            for (int j = 0; j<3; j++) {
            this->status[i][j] = s[i][j];
        }
        this->cnt = cnt;
    }
}p;
int ll;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
bool is_ok(int x, int y) {
    if (x<0 || x>2 || y<0 || y>2)return false;
    return true;
}
bool check(char(*s)[4], char(*e)[4]) {
    for (int i = 0; i<3; i++)
        for (int j = 0; j<3; j++) {
            if (s[i][j] != e[i][j])return false;
        }
    return true;
}
queue<point>que;
set<int>vis;
bool  change(char (*s)[4]) {
    
    int ans = 0;
    for (int i = 0; i < 3; i++)
    for(int j=0;j<3;j++){
        if (s[i][j] == '.')ans = ans * 10;
        else ans = ans * 10 + s[i][j] - '0';
    }
    if (vis.count(ans)) //容器中有相同 
    {
        return 0;
    }
    vis.insert(ans);//插入容器 
    return 1;
}
void bfs() {
    char temp[4][4];
    while (!que.empty()) {
        p = que.front();
        que.pop();
        if (check(p.status,e)) {
            cout << p.cnt << endl;
            return;
        }
        for (int i = 0; i<4; i++) {
            int x = p.x + dx[i];
            int y = p.y + dy[i];
            if (is_ok(x, y)) {
                memcpy(temp, p.status,sizeof(temp));
                temp[p.x][p.y] = temp[x][y];
                temp[x][y] = '.';
                if (change(temp)) {
                    que.push(point(x, y, temp, p.cnt + 1));
                }
                
            }
        }
    }
}
int main() {
    scanf("%s", a);
    int c = 0;
    int dxx, dyy;
    for (int i = 0; i<3; i++)
        for (int j = 0; j<3; j++) {
            if (a[c] == '.') {
                dxx = i, dyy= j;
            }
            s[i][j] = a[c++];
        }
    que.push(point(dxx, dyy, s, 0));
    change(s);
    c = 0;
    scanf("%s", a);
    for (int i = 0; i<3; i++)
        for (int j = 0; j<3; j++) {
            e[i][j] = a[c++];
        }
    bfs();
    return 0;
}