题目描述：输入一个m*n的地图，地图上有两种点，一种是 . 表示这个点是空地，是可以走的，另一种是 * ，表示是墙，是不能走的，然后输入一个起点和一个终点，另外有一个k输入，现在要你确定能否在转k次弯之前从起点到达终点。
解题报告：首先说下这题坑的地方，就是输入起点和终点的坐标的时候，不是按照x1,y1,x2,y2输入的，而是按照y1,x1,y2,x2的顺序输入的。这题搞了很久 ，就是一开始没有想到怎么解决得到最小转弯次数的方法，一开始试过重复访问点，但是这样超内存了，然后如果不重复访问的话又会得不到转弯次数最小的点，就是说假如一个点从一条路线上被更新过的话，下一次从另一条路线上就不能再一次更新了，即使如果按照第二次走的路线转弯的次数会更少的 话。看了别人解题报告才想到，可以这样来解决就是当走到一个点时，如果可以沿着这条线直走的话，就一直走下去，除非到了边界，或者碰到墙，同时是否将这点放入队列的话也要做出相应的 改变，因为走的时候只要不是墙都能走，但是 不能把所有的点都放进队列，所以我们可以将从没有走过并且是可以走的点放进队列，而把已经走过的点不放进队列，这样就可以解决超内存的问题了，另外，走完当前这个点之后，不要忘了把这个点标记为已经走过。并且每次走之前判断是否已经到达了终点、边界，墙。一开始用自己写的队列发现代码更长，时间也更长，后来改用deque双端队列来写，首先代码只写了5分钟，而且没有调试一次就AC了，并且时间更短，内存更小，代码也更短。这里把我手动写的队列的和用deque的代码都附上。
手写队列代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<time.h> 4 const int MAX = 100+5; 5 int T,m,n,k,x1,y1,x2,y2; 6 int xx[4] = {-1,0,1,0}; //定义移动方向 7 int yy[4] = {0,1,0,-1}; 8 int map[MAX][MAX]; 9 typedef struct node { 10 int x,y,dire,time; //dire用来保存当前的方向，time表示走到当前步为止，转弯的次数 11 node() { 12 dire = time = 0; 13 } 14 node *next; 15 }*LinkList,linklist; 16 bool bfs() { 17 LinkList head = NULL,p = NULL,temp; 18 head = new linklist; //新建队列头结点，头结点不放元素 19 p = new linklist; //便于存取节点 20 p->next = NULL; 21 p->x = x1,p->y =y1; //首先将起点加到队尾 22 head->next = p; 23 while(head->next!=NULL) { 24 temp = head->next; //将节点从队首取出 25 if(temp->x ==x2 && temp->y==y2 && temp->time-1<k) 26 return true; //判断是否已经到达终点 27 for(int i = 0;i<4;++i) { //从当前的位置向周围四个方向走 28 int xxx = temp->x + xx[i]; 29 int yyy = temp->y + yy[i]; 30 if(xxx<1||xxx>m||yyy<1||yyy>n) 31 continue; 32 while(map[xxx][yyy]==1||map[xxx][yyy]==0) { //这一步很重要，如果当前走的方向是直的，且可走，则一直走到底， 33 //但只有从没有走过的点才加入到队列中 34 if(xxx<1||xxx>m||yyy<1||yyy>n) 35 break; 36 if(xxx ==x2 && yyy==y2 && temp->time-1<k) 37 return true; 38 39 LinkList q = new linklist; 40 q->next = NULL; 41 q->x = xxx; 42 q->y = yyy; 43 q->dire = i+1; 44 q->time = temp->time; 45 if(temp->dire != q->dire) 46 q->time++; 47 if(!map[xxx][yyy]) { //从没走过的点才加入到队列中 48 q->next = p->next; 49 p->next = q; 50 p = p->next; 51 } 52 else delete q; //否则删除新建的这个点 53 map[xxx][yyy] = 1; //走过之后标记为已走过，这一顺序，这句不能放前面 54 yyy+=yy[i]; 55 xxx+=xx[i]; 56 } 57 } 58 head->next = temp->next; 59 delete temp; 60 } 61 return false; 62 } 63 64 int main() { 65 char d; 66 scanf("%d",&T); 67 while(T--) { 68 scanf("%d%d",&m,&n); 69 memset(map,0,sizeof(map)); 70 for(int i = 1;i<=m;++i) { 71 getchar(); 72 for(int j = 1;j<=n;++j) { 73 scanf("%c",&d); 74 if(d == '*') 75 map[i][j] = 2; 76 } 77 } 78 scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2); 79 printf(bfs()? "yes ":"no "); 80 } 81 return 0; 82 }
deque代码：
1 #include<cstdio> 2 #include<deque> 3 #include<iostream> 4 #include<cstring> 5 using namespace std; 6 const int MAX = 100+5; 7 int k,x1,y1,x2,y2,m,n; 8 int xx[4] = {-1,0,1,0}; 9 int yy[4] = {0,1,0,-1}; 10 class node { 11 public: 12 int map[MAX][MAX]; 13 bool bfs(); 14 private: 15 struct Linklist { 16 int x,y,dire,times; 17 Linklist() { 18 dire = times = 0; 19 } 20 }; 21 }; 22 bool node::bfs() { 23 deque<Linklist> head; 24 Linklist p; 25 p.x = x1,p.y = y1; 26 head.push_back(p); 27 deque<Linklist>::iterator iter; 28 while(head.size()!=0) { 29 iter = head.begin(); 30 for(int i = 0;i<4;++i) { 31 int xxx = iter->x + xx[i]; 32 int yyy = iter->y + yy[i]; 33 if(xxx<1||xxx>m||yyy<1||yyy>n) 34 continue; 35 while(map[xxx][yyy]!=2) { 36 if(xxx == x2 && yyy ==y2 && iter->times-1<k) 37 return true; 38 Linklist q; 39 q.x = xxx,q.y = yyy; 40 q.dire = i+1; 41 q.times = iter->times; 42 if(q.dire != iter->dire) 43 q.times++; 44 if(map[xxx][yyy]==0) 45 head.push_back(q); 46 map[xxx][yyy] = 1; 47 xxx += xx[i]; 48 yyy += yy[i]; 49 if(xxx<1||xxx>m||yyy<1||yyy>n) 50 break; 51 } 52 } 53 head.pop_front(); 54 } 55 return false; 56 } 57 int main() { 58 int T; 59 char c; 60 node temp; 61 scanf("%d",&T); 62 while(T--) { 63 scanf("%d%d",&m,&n); 64 memset(temp.map,0,sizeof(temp.map)); 65 for(int i = 1;i<=m;++i) { 66 getchar(); 67 for(int j = 1;j<=n;++j) { 68 scanf("%c",&c); 69 if(c == '*') 70 temp.map[i][j] = 2; 71 } 72 } 73 scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2); 74 printf(temp.bfs()? "yes ":"no "); 75 } 76 return 0; 77 }