A*也过不了吗???
查看原帖
A*也过不了吗???
225983
dangqishuangjiang楼主2023/1/19 19:41

为啥我的A*只有65分?

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
int n,m,ditu[35][35],q,used[35][35][35][35];
int ex,ey,sx,sy,tx,ty,ans;
int fx[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct node{
    int dis,t1,whx,why,sx,sy; 
	//whx,why是空白的位置,sx,sy是目标棋子的位置
	node (int a,int b,int c,int d,int e,int f){
		dis=a; t1=b; whx=c; why=d; sx=e; sy=f;
	}
	bool operator <(const node &a)const{
        return (dis+t1)>(a.dis+a.t1);
	}//注意此处,规定了从小到大排序的方式
	//这里的写法暂时还是不太理解
};
inline int myabs(int a){
	if(a<0) return (-a);
	return a;
}
priority_queue <node> Q;
void A(){
	while(!Q.empty()){
		node a=Q.top(); Q.pop();
		if(a.sx==tx&&a.sy==ty){
			ans=a.t1; return;
		}
        for(int i=0;i<4;i++){
    		int nx=a.whx+fx[i][0],ny=a.why+fx[i][1];
    		if(nx<1||ny<1||nx>n||ny>m) continue;
			if(!ditu[nx][ny]) { continue; }
			if(nx==a.sx&&ny==a.sy){
				if(used[a.sx][a.sy][a.whx][a.why]) continue;
                used[a.sx][a.sy][a.whx][a.why]=1;
				Q.push(node{abs(a.whx-tx)+abs(a.why-ty),a.t1+1,a.sx,a.sy,a.whx,a.why});
			}
			else{
				if(used[nx][ny][a.sx][a.sy]) continue;
                used[nx][ny][a.sx][a.sy]=1;
                Q.push(node{a.dis,a.t1+1,nx,ny,a.sx,a.sy});
			}
    	}
	}
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		scanf("%d",&ditu[i][j]);
		}
	}
	while(q--){
		scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
		ans=1e6; memset(used,0,sizeof(used));
		if(sx==tx&&sy==ty){
			printf("0\n"); continue;
		}
		Q.push(node(myabs(sx-tx)+myabs(sy-ty),0,ex,ey,sx,sy));
        used[ex][ey][sx][sy]=1; A(); 
		if(ans==1e6) {printf("-1\n");}
		else {printf("%d\n",ans);}
		while(!Q.empty()) Q.pop();
	}
	return 0;
}
2023/1/19 19:41
加载中...