本文共 1803 字，大约阅读时间需要 6 分钟。
用优先队列代替普通队列，这是不是叫权值优先搜索？
注意的是与普通队列不同，需要在进队后马上标记，不能等到访问结点的时候再标记，避免多次进队导致复杂度太高。
而普通队列是无所谓的。
// #pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef pair pii;#define pb(a) push_back(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,rvoid debug(){#ifdef ONLINE_JUDGE#else freopen("d:\\in.txt","r",stdin); freopen("d:\\out1.txt","w",stdout);#endif}char getch(){ char ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}struct point{ int x,y,t; point() {} point (int a,int b,int e) { x=a; y=b; t=e; } bool operator < (point a) const { return t>a.t; }};char plat[1010][1010];int n,m;int vis[1010][1010];int dx[]={-1,-1,0,1,1,1,0,-1};int dy[]={ 0,1,1,1,0,-1,-1,-1};int bfs(int x,int y,int aimx,int aimy){ memset(vis,INF,sizeof(vis)); priority_queue q; q.push(point(x,y,0)); vis[x][y]=0; while(!q.empty()) { point p=q.top();q.pop(); if(p.x==aimx&&p.y==aimy)return p.t; // if(vis[p.x][p.y]<=p.t)continue; // vis[p.x][p.y]=p.t; for(int d=0;d<8;d++) { point np; np.x=p.x+dx[d];np.y=p.y+dy[d];np.t=p.t+(d==plat[p.x][p.y]-'0'?0:1); if(np.x>=1&&np.x<=n&&np.y>=1&&np.y<=m&&vis[np.x][np.y]>np.t) { q.push(np); vis[np.x][np.y]=np.t; } } } return -1;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) scanf("%s",plat[i]+1); int q; scanf("%d",&q); for(int Q=1;Q<=q;Q++) { int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); int k=bfs(x1,y1,x2,y2); printf("%d\n",k); } } return 0;}
转载于:https://www.cnblogs.com/BMan/p/3272455.html
