//hdu 1728背景：wa了29次，最后还是借助别人的想法。
第一种想法：把visit数组的每一个位置储存为到达当前坐标点所需要的最小转弯数，最后对于每个走过的点都是到达该点的最小转弯数。这样的最小转弯数点又递推下一个最小转弯数点…..这样层层递推直到终点。
第二种方法:在普通情况下的bfs是每一步都走距离为1，，找出所有的下一步放入队列，然后这样层层递推，而这个题中我们bfs每次由该点出去所有四个方向上的点加入队列，这样这些点都只多转了一次弯，想当于把距离加一变成转弯数加一。
求最短距离就把每次增加一步作为bfs的变量。求最小转弯数就把每次增加一次转弯作为bfs的变量。好和谐！
第一种想法代码：#include<map>#include<set>#include<stack>#include<queue>#include<vector>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define M 209#define INF 100000000#define LL long long intusing namespace std;int t,n,m,k,x1,x2,y1,y2,ans=INF,dir[4][2]={-1,0,0,1,1,0,0,-1};char maps[M][M];int visit[M][M];struct place{int x,y,step,last;}temp1,temp2;void bfs(void){temp1.x=x1;temp1.y=y1;temp1.step=0;temp1.last=-1;queue<place> q;q.push(temp1);while(!q.empty()){temp1=q.front();q.pop();if(temp1.step > k) continue;if(temp1.x == x2 && temp1.y == y2){if(temp1.step < ans) ans=temp1.step;if(ans <= k) return;}for(int i=0;i < 4;i++){if(temp1.x+dir[i][0] > 0 && temp1.x +dir[i][0] <= n && temp1.y+dir[i][1] > 0 && temp1.y+dir[i][1] <= m){temp2.x=temp1.x+dir[i][0];temp2.y=temp1.y+dir[i][1];if(temp1.last != -1 && temp1.last != i) temp2.step=temp1.step+1;else temp2.step=temp1.step;temp2.last=i;if(maps[temp2.x][temp2.y] == '.' && temp2.step <= visit[temp2.x][temp2.y]){visit[temp2.x][temp2.y]=temp2.step;q.push(temp2);}}}}}int main(void){scanf("%d",&t);while(t–){ans=INF;//memset(visit,100000000001,sizeof(visit));for(int i=0;i < M;i++) for(int j=0;j < M;j++) visit[i][j]=INF;//printf("visit:%d %d\n",visit[0][0],visit[1][2]);scanf("%d%d",&n,&m);getchar();for(int i=1;i <= n;i++){for(int j=1;j <= m;j++){scanf("%c",&maps[i][j]);}getchar();}scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);bfs();if(ans <= k) printf("yes\n");else printf("no\n");}return 0;}
到尽头，也许快乐，或有时孤独，如果心在远方，
