调了一上午,总是WA 12
查看原帖
调了一上午,总是WA 12
520748
_Ch1F4N_楼主2023/1/8 10:46

如题,谁来帮忙调一下。

#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();
		
	}
}
2023/1/8 10:46
加载中...