蓝桥杯历届试题-九宫重排 （C++代码）

解题思路:

与大家分享大佬文章：
原文：https://blog.csdn.net/Jaster_wisdom/article/details/79707054

参考代码:

#include <iostream>
#include <queue>
#include <string>
#include<cstring>
#include <set>
using namespace std;
 
#define N 10005;
 
char mp[3][3],gp[3][3];
int dir[4][2] = {0,1,1,0,-1,0,0,-1}; //表示上下左右四个方向
 
struct node{  //结点代表一种状态
    int x,y;
    int step;
    char cur_mp[3][3]; //当前图案
    node(int x,int y,int step){
        this->x = x;
        this->y = y;
        this->step = step;
    }
};
 
set<int> st;
queue<node> q;
 
bool check(node cur){ //判断是否达到终态
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(cur.cur_mp[i][j]!=gp[i][j])
                return false;
        }
    }
    return true;
}
 
int cal(node cur){  //将每种状态映射到一个整数
    int result = 0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(cur.cur_mp[i][j]!='.')
                result = result*10+(cur.cur_mp[i][j]-'0');
            else
                result = result*10+9;
        }
    }
    return result;
}
 
void bfs(){
    st.clear();
    if(!q.empty())
        st.insert(cal(q.front()));
    while(!q.empty()){
        node cur = q.front();
        q.pop();
        if(check(cur)){  //检查是否到了终态
            cout<<cur.step<<endl;
            return;
        }
        //改动空格周围的四个数码块
        for(int i=0;i<4;i++){
            int xx = cur.x + dir[i][1];
            int yy = cur.y + dir[i][0];
            if(xx<0 || xx>2 || yy<0 || yy>2)
                continue;    //边界检查
            node nt = node(xx,yy,cur.step+1);
            memcpy(nt.cur_mp,cur.cur_mp,sizeof(cur.cur_mp));
            int temp = nt.cur_mp[xx][yy];
            nt.cur_mp[xx][yy] = '.';
            nt.cur_mp[cur.x][cur.y] = temp;
            int val = cal(nt);
            if(st.find(val) != st.end()) //去掉重复的图
                continue;
            st.insert(val);
            q.push(nt);
        }
    }
    cout<<-1<<endl;
}
 
int main(){
    string str1,str2;
    cin>>str1>>str2;
    int bx=0,by=0;
    while(!q.empty())
        q.pop();
    int len = 0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            mp[i][j] = str1[len++];
            if(mp[i][j]=='.'){
                bx = i;
                by = j;
            }
        }
    }
    node cur = node(bx,by,0);
    memcpy(cur.cur_mp,mp,sizeof(mp));
    q.push(cur);
    len = 0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            gp[i][j] = str2[len++];
        }
    }
    bfs();
    return 0;
}