如题,谁来帮忙调一下。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int qpow(int a,int b){
if(b==0) return 1;
if(b==1) return a;
int res=qpow(a,b/2);
res*=res;
if(b%2==1) res*=a;
return res;
}
int end[4][4];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
struct Map{
int m[4][4];
int step;
bool operator<(const Map&x) const {
int X,Y,w,u;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
if(m[i][j]==0){
X=i,Y=j;
}
if(x.m[i][j]==0){
w=i;
u=j;
}
}
}
int res1=step+abs(X-2)+abs(Y-2);
int res2=x.step+abs(w-2)+abs(u-2);
return res1>res2;
}
}start;
int val(Map a){
int res=0;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
res+=qpow(10,(i-1)*3+(j-1))*(a.m[i][j]+1);
}
}
return res;
}
int f=0;
int h(Map a){
int res=0;
int chifan=0;
int x,y;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
if(a.m[i][j]==chifan){
x=i,y=j;
}
}
}
int w,u;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
if(start.m[i][j]==chifan){
w=i,u=j;
}
}
}
res = abs(x-w)+abs(y-u);
return res;
}
map<int,int> use;
int D=24;
void bfs(){
priority_queue<Map> q;
q.push(start);
use[val(start)]=1;
while(q.size()>0){
Map now=q.top();
q.pop();
if(now.step>D){
use.clear();
return ;
}
int flag=0;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
if(now.m[i][j]!=end[i][j]) flag=1;
}
}
if(flag==0){
f=1;
cout<<now.step;
use.clear();
return ;
}
Map nxt;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
nxt.m[i][j]=now.m[i][j];
}
}
int X,Y;
nxt.step=now.step+1;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
if(nxt.m[i][j]==0){
X=i;
Y=j;
}
}
}
for(int k=0;k<=3;k++){
int nx=X+dx[k];
int ny=Y+dy[k];
if(nx>=1&&nx<=3&&ny>=1&&ny<=3){
swap(nxt.m[X][Y],nxt.m[nx][ny]);
if(use[val(nxt)]==0){
use[val(nxt)]=1;
q.push(nxt);
}
swap(nxt.m[X][Y],nxt.m[nx][ny]);
}
}
}
}
signed main(){
srand(time(0));
end[1][1]=1;
end[1][2]=2;
end[1][3]=3;
end[2][1]=8;
end[2][2]=0;
end[2][3]=4;
end[3][1]=7;
end[3][2]=6;
end[3][3]=5;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
char c;
cin>>c;
start.m[i][j]=(int)(c-'0');
}
}
start.step=0;
while(f==0){
D++;
bfs();
}
}