好久之前感觉见过这道题?
然后调了n久n久n久。。。。
不知道别的写法会犯什么奇奇怪怪的问题,反正就是不能A。。。
目测只能用这种SPFA的方法了,而且一定要把jl[i][j][k]分开清清楚楚的!表示到达(i,j)这个点持续的方向为k
#include#include #include #include #define INF 1e9 using namespace std; struct hh{int x,y,fx;}; const int c[5][2]={{0,0},{1,0},{0,1},{-1,0},{0,-1}}; int n,i,j,bx,by,ex,ey,jl[105][105][5]; char a[105][105];bool vis[105][105][5]; void bfs() { queue q; memset(jl,0x7f,sizeof(jl)); q.push((hh){bx,by,1}); q.push((hh){bx,by,2}); q.push((hh){bx,by,3}); q.push((hh){bx,by,4}); jl[bx][by][1]=jl[bx][by][2]=jl[bx][by][3]=jl[bx][by][4]=0; vis[bx][by][1]=vis[bx][by][2]=vis[bx][by][3]=vis[bx][by][4]=0; while (!q.empty()) { hh now=q.front(); q.pop(); vis[now.x][now.y][now.fx]=0; for (int i=1;i<=4;i++) { int xx=now.x+c[i][0],yy=now.y+c[i][1],gw=jl[now.x][now.y][now.fx]; if (xx>n || yy>n || xx<1 || yy<1 || a[xx][yy]=='x') continue; if (now.fx!=i) gw++; if (jl[xx][yy][i]>gw) { jl[xx][yy][i]=gw; if (!vis[xx][yy][i]) vis[xx][yy][i]=1,q.push((hh){xx,yy,i}); } } } int t1=min(jl[ex][ey][1],jl[ex][ey][2]); int t2=min(jl[ex][ey][3],jl[ex][ey][4]); if (min(t1,t2)>INF) printf("-1"); else printf("%d",min(t1,t2)); } int main() { scanf("%d",&n); for (i=1;i<=n;i++) for (j=1;j<=n;j++) { char ch=getchar(); while (ch!='x' && ch!='A' && ch!='B' && ch!='.') ch=getchar(); a[i][j]=ch; if (a[i][j]=='A') bx=i,by=j; if (a[i][j]=='B') ex=i,ey=j; } bfs(); }