题目大意：给定一个有坏点的网格图，从A点走到B点，，要求拐弯最少
裸SPFA……在状态那里记录下方向就好了
水水更健康~~
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 10100#define P(x,y) ((x)*n-n+(y))using namespace std;const int dx[]={0,0,1,-1};const int dy[]={1,-1,0,0};int n,A,B;int map[M],f[M<<2];void SPFA(){static int q[65540];static bool v[M<<2];static unsigned short r,h;int i;memset(f,0x3f,sizeof f);for(i=0;i<4;i++)f[q[++r]=A<<2|i]=0,v[A<<2|i]=true;while(r!=h){int x=q[++h];v[x]=false;int _x=((x>>2)-1)/n+1,_y=((x>>2)-1)%n+1,_dir=x&3;for(i=0;i<4;i++){int xx=_x+dx[i],yy=_y+dy[i];if(xx<=0||yy<=0||xx>n||yy>n)continue;if(map[P(xx,yy)]) continue;int y=P(xx,yy)<<2|i;if(f[y]>f[x]+(i!=_dir) ){f[y]=f[x]+(i!=_dir);if(!v[y])v[y]=true,q[++r]=y;}}}}int main(){int i,j;cin>>n;for(i=1;i<=n;i++){static char s[M];scanf("%s",s+1);for(j=1;j<=n;j++)switch(s[j]){case 'x':map[P(i,j)]=1;break;case 'A':A=P(i,j);break;case 'B':B=P(i,j);break;}}SPFA();cout<<min(min(f[B<<2|0],f[B<<2|1]),min(f[B<<2|2],f[B<<2|3]))<<endl;return 0;}
这一生我只牵你的手，因为今生有你早已足够。
