（BFS）poj2935-Basic Wall Maze

题目与最基本的BFS迷宫的区别就是有一些障碍，可以通过建立三维数组，标记某个地方有障碍不能走。另一个点是输出路径，对此建立结构体时要建立一个pre变量，指向前一个的下标。这样回溯（方法十分经典）就可以顺利的输出。

这道题难度的确很小，可是我却花了近两个小时才顺利AC，实在是现在水平太不足了，要努力学习的真的是有好多啊。不管怎样，尽力吧。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 struct grid

 {

     int x,y;//坐标

     int pre;//回溯前一个的下标

     int dir;

 }point[];

 int si,sj,ei,ej,a[],dir[][][],direction[][]={{-,},{,},{,},{,-}},vi[][];

 int  bfs()

 {

     memset(vi,,sizeof(vi));

     int front=,tail=;

     point[front].x=si;

     point[front].y=sj;

     point[front].pre=-;

     grid temp,temp2;

     vi[si][sj]=;

     while(front<tail)

     {

         temp=point[front];

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

         {

             if(dir[temp.x][temp.y][i]==){continue;}

             else

             {

                 temp2.x=temp.x+direction[i][];

                 temp2.y=temp.y+direction[i][];

                 temp2.dir=i;

                 if(vi[temp2.x][temp2.y])

                     continue;

                 else

                 {

                     temp2.pre=front;

                     vi[temp2.x][temp2.y]=;

                     point[tail++]=temp2;

                     if(temp2.x==ei&&temp2.y==ej)

                         return (tail-);

                 }

             }

         }

         front++;

     }

 }

 void print(int x)//经典的输出方式

 {

     if(x>)

         {

         print(point[x].pre);

         if(point[x].dir==)

         {

             printf("N");

         }

         else if(point[x].dir==)

         {

             printf("E");

         }

         else if(point[x].dir==)

         {

             printf("S");

         }

         else printf("W");

         }

 }

 int main()

 {

     while(scanf("%d%d",&sj,&si))

     {

         int i,j,k,an;

         if(si==&&sj==)

             break;

         scanf("%d%d",&ej,&ei);

         memset(dir,,sizeof(dir));

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

         {

             dir[][i][]=;

             dir[][i][]=;

             dir[i][][]=;

             dir[i][][]=;

         }

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

         scanf("%d %d %d %d",&a[],&a[],&a[],&a[]);//注意数据是行列与平常不同的

         if(a[]==a[])

         {

             for(k=min(a[],a[])+;k<max(a[],a[])+;k++)

             {

                 dir[a[]+][k][]=;

                 dir[a[]][k][]=;

             }

         }

         else

         {

             for(k=min(a[],a[])+;k<max(a[],a[])+;k++)

             {

                 dir[k][a[]+][]=;

                 dir[k][a[]][]=;

             }

         }

     }

     an=bfs();

     print(an);

     puts("");

     }

     return ;

 }

巴特西

（BFS）poj2935-Basic Wall Maze

最新文章

热门文章