HDU 1728 逃离迷宫 BFS题

题目描述：输入一个m*n的地图，地图上有两种点，一种是 . 表示这个点是空地，是可以走的，另一种是 * ，表示是墙，是不能走的，然后输入一个起点和一个终点，另外有一个k输入，现在要你确定能否在转k次弯之前从起点到达终点。

解题报告：首先说下这题坑的地方，就是输入起点和终点的坐标的时候，不是按照x1,y1,x2,y2输入的，而是按照y1,x1,y2,x2的顺序输入的。这题搞了很久，就是一开始没有想到怎么解决得到最小转弯次数的方法，一开始试过重复访问点，但是这样超内存了，然后如果不重复访问的话又会得不到转弯次数最小的点，就是说假如一个点从一条路线上被更新过的话，下一次从另一条路线上就不能再一次更新了，即使如果按照第二次走的路线转弯的次数会更少的话。看了别人解题报告才想到，可以这样来解决就是当走到一个点时，如果可以沿着这条线直走的话，就一直走下去，除非到了边界，或者碰到墙，同时是否将这点放入队列的话也要做出相应的改变，因为走的时候只要不是墙都能走，但是不能把所有的点都放进队列，所以我们可以将从没有走过并且是可以走的点放进队列，而把已经走过的点不放进队列，这样就可以解决超内存的问题了，另外，走完当前这个点之后，不要忘了把这个点标记为已经走过。并且每次走之前判断是否已经到达了终点、边界，墙。一开始用自己写的队列发现代码更长，时间也更长，后来改用deque双端队列来写，首先代码只写了5分钟，而且没有调试一次就AC了，并且时间更短，内存更小，代码也更短。这里把我手动写的队列的和用deque的代码都附上。

手写队列代码：

 #include<cstdio>

 #include<cstring>

 #include<time.h>

 const int MAX = +;

 int T,m,n,k,x1,y1,x2,y2;

 int xx[] = {-,,,};  //定义移动方向

 int yy[] = {,,,-};

 int map[MAX][MAX];

 typedef struct node {

     int x,y,dire,time;   //dire用来保存当前的方向，time表示走到当前步为止，转弯的次数

     node() {

         dire = time = ;

     }

     node *next;

 }*LinkList,linklist;

 bool bfs() {

     LinkList head = NULL,p = NULL,temp;

     head = new linklist;  //新建队列头结点，头结点不放元素

     p = new linklist; //便于存取节点

     p->next = NULL;

     p->x = x1,p->y =y1;  //首先将起点加到队尾

     head->next = p;

     while(head->next!=NULL) {

         temp = head->next;   //将节点从队首取出

         if(temp->x ==x2 && temp->y==y2 && temp->time-<k)

         return true;     //判断是否已经到达终点

         for(int i = ;i<;++i) {   //从当前的位置向周围四个方向走

             int xxx = temp->x + xx[i];

             int yyy = temp->y + yy[i];

             if(xxx<||xxx>m||yyy<||yyy>n)

             continue;

             while(map[xxx][yyy]==||map[xxx][yyy]==) { //这一步很重要，如果当前走的方向是直的，且可走，则一直走到底，

             //但只有从没有走过的点才加入到队列中

                 if(xxx<||xxx>m||yyy<||yyy>n)

                 break;

                 if(xxx ==x2 && yyy==y2 && temp->time-<k)

                 return true;

                 LinkList q = new linklist;

                 q->next = NULL;

                 q->x = xxx;

                 q->y = yyy;

                 q->dire = i+;

                 q->time = temp->time;

                 if(temp->dire != q->dire)

                 q->time++;

                 if(!map[xxx][yyy]) {  //从没走过的点才加入到队列中

                     q->next = p->next;

                     p->next = q;

                     p = p->next;

                 }

                 else delete q;  //否则删除新建的这个点

                 map[xxx][yyy] = ;  //走过之后标记为已走过，这一顺序，这句不能放前面

                 yyy+=yy[i];

                 xxx+=xx[i];

             }

         }

         head->next = temp->next;

         delete temp;

     }

     return false;

 }

 int main() {

     char d;

     scanf("%d",&T);

     while(T--) {

         scanf("%d%d",&m,&n);

         memset(map,,sizeof(map));

         for(int i = ;i<=m;++i) {

             getchar();

             for(int j = ;j<=n;++j) {

                 scanf("%c",&d);

                 if(d == '*')

                 map[i][j] = ;

             }

         }

         scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);

         printf(bfs()? "yes\n":"no\n");

     }

     return ;

 }

deque代码：

 #include<cstdio>

 #include<deque>

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int MAX = +;

 int k,x1,y1,x2,y2,m,n;

 int xx[] = {-,,,};

 int yy[] = {,,,-};

 class node {

 public:

     int map[MAX][MAX];

     bool bfs();

 private:

     struct Linklist {

         int x,y,dire,times;

         Linklist() {

             dire = times  = ;

         }

     };

 };

 bool node::bfs() {

     deque<Linklist> head;

     Linklist p;

     p.x = x1,p.y = y1;

     head.push_back(p);

     deque<Linklist>::iterator iter;

     while(head.size()!=) {

         iter = head.begin();

         for(int i = ;i<;++i) {

             int xxx = iter->x + xx[i];

             int yyy = iter->y + yy[i];

             if(xxx<||xxx>m||yyy<||yyy>n)

             continue;

             while(map[xxx][yyy]!=) {

                 if(xxx == x2 && yyy ==y2 && iter->times-<k)

                 return true;

                 Linklist q;

                 q.x = xxx,q.y = yyy;

                 q.dire = i+;

                 q.times = iter->times;

                 if(q.dire != iter->dire)

                 q.times++;

                 if(map[xxx][yyy]==)

                 head.push_back(q);

                 map[xxx][yyy] = ;

                 xxx += xx[i];

                 yyy += yy[i];

                 if(xxx<||xxx>m||yyy<||yyy>n)

                 break;

             }

         }

         head.pop_front();

     }

     return false;

 }

 int main() {

     int T;

     char c;

     node temp;

     scanf("%d",&T);

     while(T--) {

         scanf("%d%d",&m,&n);

         memset(temp.map,,sizeof(temp.map));

         for(int i = ;i<=m;++i) {

             getchar();

             for(int j = ;j<=n;++j) {

                 scanf("%c",&c);

                 if(c == '*')

                 temp.map[i][j] = ;

             }

         }

         scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);

         printf(temp.bfs()? "yes\n":"no\n");

     }

     return ;

 }

巴特西

HDU 1728 逃离迷宫 BFS题

最新文章

热门文章