题解 P1649 【[USACO07OCT]障碍路线Obstacle Course】

题解by：redbag 其实就是暴力，一个格子一个格子的搜，每次只扩展一个（因为不一定需要走到底） 然后扩展之后入队， 注意：每个点不止入队一次，因为可能之后找到了更优的方案（毕竟是拐弯次数啊） 然后具体见代码 ```cpp #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<iostream> #include<algorithm> using namespace std; int read(){ char s; int k=0,base=1; while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9')); if(s==EOF)exit(0); if(s=='-')base=-1,s=getchar(); while(s>='0'&&s<='9') { k=(k<<1)+(k<<3)+(s-'0'); s=getchar(); } return k*base; } void write(int x) { if(x<0){putchar('-');write(-x);} else{if(x/10)write(x/10);putchar(x%10+'0');} } int n; int sx,sy,tx,ty; int a[110][110]; int d[110][110]; struct node { int x,y; int d; int f; }; int ans; int fx[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; queue<node> q; int main() { n=read(); char ch; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) {//只有1的地方可以走 ch=getchar(); while (ch!='A'&&ch!='B'&&ch!='.'&&ch!='x') ch=getchar(); //神奇读入，只要不是自己要的就丢掉 if (ch=='A') a[i][j]=1,sx=i,sy=j; else if (ch=='B') a[i][j]=1,tx=i,ty=j; else if (ch=='.') a[i][j]=1;//标记，s：起点，t：终点 } } node aa;//起点入队 aa.x=sx;aa.y=sy;aa.d=0;aa.f=-1; memset(d,1,sizeof(d)); a[aa.x][aa.y]=233;//和'x'分开，因为一个点可能反复入队 //（第一次找到的不一定是最优解，亲测30分） d[aa.x][aa.y]=0;//打标记 q.push(aa); ans=23333333; while (!q.empty()) { node u; u=q.front(); q.pop(); if (u.d>ans) continue;//搜索剪枝，如果转弯次数大于ans就不用搜了 for (int i=0;i<=3;i++) {//四个方向一个一个的去扫 node v; v.x=u.x+fx[i][0]; v.y=u.y+fx[i][1]; v.f=i; if (u.f==-1||u.f==v.f) v.d=u.d; else v.d=u.d+1; //v.f存的是这一步走的方向，如果上一步没走或者和这一步方向一样，那么拐弯次数不变 if (v.x<1||v.y<0||v.x>n||v.y>n) continue;//越界 if ((a[v.x][v.y]!=1&&v.d>d[v.x][v.y])||a[v.x][v.y]==0) continue; //如果扫过并且这次并不是更优，或者是x（走不了），就不搜了 a[v.x][v.y]=233;//标记 d[v.x][v.y]=v.d;//记录 if (v.x==tx&&v.y==ty)//到终点了，更新ans，不用入队 { ans=min(ans,v.d); continue; } q.push(v); } } if (ans!=23333333) printf("%d\n",ans); else//输出 printf("-1"); return 0; } ```