BFS求助

P2199 最后的迷宫

有错的地方我给你标出来了: ``` #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int n,m,ans; char ch; int tx,ty,sx,sy; int p[20000]; int a[20000]; bool v[20000]; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; int ddx[8]={-1,1,0,0,-1,-1,1,1}; int ddy[8]={0,0,-1,1,-1,1,-1,1}; int f(int x,int y) { return (x-1)*m+y-1;//y也要-1 } struct point { int x; int y; int s; }; void init() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[f(i,j)]=p[f(i,j)]; memset(v,0,sizeof(v)); ans=0x3f3f3f3f; } void bfs() { queue<point> q; point t,u; t.x=sx; t.y=sy; t.s=0; q.push(t); while(!q.empty()) { t=q.front(); q.pop(); if(a[f(t.x,t.y)]==2) ans=min(ans,t.s); for(int i=0;i<4;i++) { int xx=t.x+dx[i],yy=t.y+dy[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[f(xx,yy)]!=1&&!v[f(xx,yy)]) { v[f(xx,yy)]=1;//标记写这里,不然会排到队尾 u.x=xx; u.y=yy; u.s=t.s+1; q.push(u); } } } } void work() { if(sx==tx&&sy==ty) { printf("0\n"); return; } init(); a[f(tx,ty)]=2; for(int i=0;i<8;i++) { int xx=tx+ddx[i],yy=ty+ddy[i]; while(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[f(xx,yy)]!=1) { a[f(xx,yy)]=2; xx+=ddx[i]; yy+=ddy[i]; } } bfs(); if(ans==0x3f3f3f3f) printf("Poor Harry\n"); else printf("%d\n",ans); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>ch; if(ch=='X') p[f(i,j)]=1; } while(cin>>tx>>ty>>sx>>sy&&tx&&ty&&sx&&sy) work(); return 0; } ```
by mons @ 2022-08-22 18:30:04


~~不谢~~
by mons @ 2022-08-22 18:30:49


|