蓝桥杯历届试题-九宫重排 （C++代码）慢慢写，慢慢攻略

解题思路:
    第一法，裸BFS，无任何数据结构进行嵌套
参考代码:

#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn_3len=10000;
const int maxn=15;
const int map_maxn=1000;
const int dir[4][2]={1,0,-1,0,0,1,0,-1}; //方向向量 
char beg[maxn],fin[maxn];
int beg_[maxn_3len][maxn][maxn]={0},fin_[maxn][maxn]={0};
//int vis[map_maxn][map_maxn];
struct state{
 int x,y;
 int step;
 int cnt;
};
void print_map(int pos){
 for(int i=1;i<=3;i++){
  for(int j=1;j<=3;j++){
   cout<<beg_[pos][i][j]<<' ';
  }
  cout<<endl;
 }
 cout<<endl;
}
void plan_map(int pos,int last){
 for(int i=1;i<=3;i++){
  for(int j=1;j<=3;j++){
   beg_[pos][i][j]=beg_[last][i][j];
  }
 }
}
bool check_out(int pos){
 bool flag=true;
 for(int i=1;i<=3;i++){
  for(int j=1;j<=3;j++){
   if(beg_[pos][i][j]!=fin_[i][j]){
    flag=false;
   }
  }
 }
 return flag;
}
bool check_is(state s){
 //if(!vis[s.x][s.y]&&s.x>=1&&s.x<=3&&s.y>=1&&s.y<=3){
 if(s.x>=1&&s.x<=3&&s.y>=1&&s.y<=3){
  return true;
 }else{
  return false;
 }
}
int bfs(state st){
 queue<state> q;
 state now,next;
 int pos=1;  //用来表示beg_数组搜索的层数 
 q.push(st);
 //vis[st.x][st.y]=1;
 while(!q.empty()){
  now=q.front();
  q.pop();
  //cout<<now.cnt<<endl;
  //print_map(now.cnt);
  if(check_out(now.cnt)){
   return now.step;
  }
  for(int i=0;i<4;i++){
   next.x=now.x+dir[i][0];
   next.y=now.y+dir[i][1];
   next.step=now.step+1;
   //insert the new beg_ ,but how?????
   next.cnt=pos++;
   plan_map(next.cnt,now.cnt);
   swap(beg_[next.cnt][next.x][next.y],beg_[next.cnt][now.x][now.y]);
   if(check_is(next)){
    q.push(next);
    //vis[next.x][next.y]=1;
   }
  }
 }
 return -1;
}
int main(){
 hh;
 cin>>beg;
 cin>>fin;
 state start_point;
 for(int i=1,pos=0;i<=3;i++){
  for(int j=1;j<=3;j++){
   if(beg[pos]!='.'){
    beg_[0][i][j]=beg[pos]-'0';
   } else{
    beg_[0][i][j]=0;
    start_point.x=i;
    start_point.y=j;
    start_point.step=0;
    start_point.cnt=0;
   }
   if(fin[pos]!='.'){
    fin_[i][j]=fin[pos++]-'0'; //第二次再自增  
   }else{
    fin_[i][j]=0;
    pos++; 
   }
  }
 }
 cout<<bfs(start_point)<<endl;
 return 0;
}
// 超时，炸内存，还 运行错误 67%

准备再搞一发Hash进行嵌套。