3337

智慧的小石头 · 发表于 2022-7-21 08:40:24

目描述
全屏
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入
输入初始状态，一行九个数字，空格用0表示

输出
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入1
283104765

样例输出1
4

智慧的小石头 · 发表于 2022-7-21 08:41:03

代码
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N=10;
struct node{
int s[N];
int dis;
};
int g[]={1,2,3,8,0,4,7,6,5};
//int g[]={1,0,3,8,2,4,7,6,5};
int start[N];
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int factory[]={1,1,2,6,24,120,720,5040,40320,362880};
int visit[400000];
bool cantor(int str[],int n){
int ans=0;
for(int i=0;i<n;i++){
      int cnt=0;
      for(int j=i+1;j<n;j++){
         if(str[i]>str[j])
            cnt++;
      }
      ans+=cnt*factory[n-i-1];
}
if(!visit[ans]){
      visit[ans]=1;
      return 1;
}
else
      return 0;
}
int bfs(){
int id;
cantor(start,9);
queue<node> q;
node q_1;
memcpy(q_1.s,start,sizeof(start));
q_1.dis=0;
q.push(q_1);

while(!q.empty()){
      node a=q.front();
      q.pop();
      for(int i=0;i<9;i++)
         if(a.s[i]==0)
            id=i;
      int x=id/3;
      int y=id%3;
      for(int i=0;i<4;i++){
         int nx=x+dx[i];
         int ny=y+dy[i];
         if(nx>=3||nx<0||ny>=3||ny<0)continue;
         node b;
         int nz=3*nx+ny;
         memcpy(b.s,a.s,sizeof(a.s));
         swap(b.s[id],b.s[nz]);
         b.dis=a.dis+1;

         if(memcmp(b.s,g,sizeof(g)) == 0){
            return b.dis;
         }
         else if(cantor(b.s,9)){
            q.push(b);
         }
      }
}
return -1;
}
int main(){
string s;
cin>>s;
if(s=="123804765")
{
cout<<0;
return 0;
}
for(int i=0;i<s.length();i++){
      start[i]=s[i]-'0';
}
int num=bfs();
cout<<num;
return 0;
}