如果把我在涵式cmp的if(a.f==b.f)這段刪除 是可以算出答案 只是實際走出來的效率就不及A*應有的

所以就吃tle了

因此我想說如果替每個Push進去的元素增加一個紀錄順序的int

若兩個f值相等則先pop出較晚進去的

這樣看起來應該會比較接近a*應有的感覺(?

但是最後跑出來是錯誤的

不知道是我本身的code錯誤

或是我的想法就錯了

還煩請版上的大大幫我解惑一下

感謝><

#include<bits/stdc++.h> struct record{ int f=0,h=0,g=0,x,y,px,py; int order=0;//g:current h:heuristic }; struct cmp{ bool operator()(record a,record b){ if(a.f==b.f)return a.order<b.order; return a.f>b.f; } }; int n,gx,gy,order;//gx:goal x / gy:goal y char maze[1000][1000]; bool closelist[1000][1000]; record mazedata[1000][1000]; std::priority_queue<record,std::vector,cmp>openlist; void reset(){ order=0; for(int i=0;i<1000;i++){ for(int j=0;j<1000;j++){ closelist[i][j]=false; mazedata[i][j].f=0;mazedata[i][j].x=i;mazedata[i][j].y=j; } } while(!openlist.empty())openlist.pop(); } void astar_algorithm(int x,int y){ int g,dx[4]={-1,0,0,1},dy[4]={0,-1,1,0}; while(!openlist.empty()){ g=mazedata[x][y].g; if(x==gx&&y==gy){ closelist[x][y]=true; break; } for(int i=0;i<4;i++){ if(x+dx[i]<n&&x+dx[i]>=0&&y+dy[i]<n&&y+dy[i]>=0&&closelist[x+dx[i]][y+dy[i]]==false&&maze[x+dx[i]][y+dy[i]]=='.'){ if(mazedata[x+dx[i]][y+dy[i]].f!=0){ if(g+1+mazedata[x+dx[i]][y+dy[i]].h<mazedata[x+dx[i]][y+dy[i]].f){ mazedata[x+dx[i]][y+dy[i]].px=x; mazedata[x+dx[i]][y+dy[i]].py=y; mazedata[x+dx[i]][y+dy[i]].f=g+1+mazedata[x+dx[i]][y+dy[i]].h; mazedata[x+dx[i]][y+dy[i]].g=g+1; mazedata[x+dx[i]][y+dy[i]].order=++order; openlist.push(mazedata[x+dx[i]][y+dy[i]]); } }else{ mazedata[x+dx[i]][y+dy[i]].h=abs(x+dx[i]-gx)+abs(y+dy[i]-gy); mazedata[x+dx[i]][y+dy[i]].g=g+1; mazedata[x+dx[i]][y+dy[i]].f=mazedata[x+dx[i]][y+dy[i]].h+mazedata[x+dx[i]][y+dy[i]].g; mazedata[x+dx[i]][y+dy[i]].px=x; mazedata[x+dx[i]][y+dy[i]].py=y; mazedata[x+dx[i]][y+dy[i]].order=++order; openlist.push(mazedata[x+dx[i]][y+dy[i]]); } } } closelist[x][y]=true; openlist.pop(); x=openlist.top().x; y=openlist.top().y; } } int main(){ std::ios::sync_with_stdio(false); int m,a,b,x,y; int tx,ty; std::cin>>n>>m; for(int i=0;i<n;i++){ for(int k=0;k<n;k++){ std::cin>>maze[i][k]; } } while(m--){ reset(); std::cin>>a>>b>>x>>y; if(maze[a][b]=='X'||maze[x][y]=='X'){ std::cout<<"ERROR\n"; continue; }else{ gx=x; gy=y; mazedata[a][b].g=0; mazedata[a][b].order=0; openlist.push(mazedata[a][b]); astar_algorithm(a,b); if(closelist[x][y]==false)std::cout<<"-1\n"; else { std::cout<<mazedata[x][y].g<<std::endl; } } } }