分析：这题目挺经典的。。求最小拐点数，这个好像印象中遇见了很多次？ 直接spfa就好了，但是注意储存方向，四个方向都有可能，所以都要算上。。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; struct node { int x,y,dir,dis; }now,next; bool operator <(const node&a,const node&b) { return a.dis>b.dis; } priority_queue <node>q; const int dx[4]={0,1,0,-1}; const int dy[4]={1,0,-1,0}; int sx,sy,ex,ey; bool bz[105][105]; int dis[110][110][4]; int main() { scanf("%d%d",&m,&n); fo(i,1,n) { fo(j,1,m) { char ch=getchar(); while (ch!='C'&&ch!='.'&&ch!='*')ch=getchar(); if (ch=='*')bz[i][j]=1; if (ch=='C') { if (!sx) { sx=i,sy=j; } else ex=i,ey=j; } } } memset(dis,127,sizeof(dis)); now.x=sx,now.y=sy,now.dis=0; fo(i,0,3) { now.dir=i; q.push(now); dis[sx][sy][i]=0; } while (!q.empty()) { now=q.top(); q.pop(); int k=now.dir; next=now; while (next.x+dx[k]>=1&&next.x+dx[k]<=n&&next.y+dy[k]>=1&&next.y+dy[k]<=m&&!bz[next.x+dx[k]][next.y+dy[k]]&&dis[next.x+dx[k]][next.y+dy[k]][k]>next.dis) { next.x+=dx[k];next.y+=dy[k]; dis[next.x][next.y][k]=dis[now.x][now.y][k]; q.push(next); } next=now; next.dis++; fo(k,0,3) if (dis[now.x][now.y][k]>now.dis+1) { dis[now.x][now.y][k]=now.dis+1; next.dir=k; q.push(next); } } int ans=1000000000; fo(k,0,3) ans=min(ans,dis[ex][ey][k]); printf("%d\n",ans); }