ZZULI_SummerPractice(3)nbsp;POJnbsp;3984…

本文主要是介绍ZZULI_SummerPractice(3)nbsp;POJnbsp;3984…，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C - 迷宫问题 _p

Time Limit: 1000MS

Memory Limit: 65536K

64bit IO Format: %I64d & %I64u

[Submit] [Go Back] [Status]

Description

定义一个二维数组：



int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,


};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0)


(1, 0)


(2, 0)


(2, 1)


(2, 2)


(2, 3)


(2, 4)


(3, 4)


(4, 4)

这题要是求最短距离的话估计都能做出来，但是一加上路径的话就不好做了（幸亏我事先早有准备），用一个数组一旦有数据存入队列，则在数组中记下他的前驱，这样，最后倒序查找就能找到啦，然后输出就可以啦！

代码：

#include<stdio.h>

#include<string.h>

typedef struct point{
   int x,y,step;

}target;

int map[5][5],flag[4][2]={0,1,0,-1,-1,0,1,0};

target que[30],dir[5][5];

int BFS(target start)

{
   int end,top,i;
   target in,next;
   end=top=0;
   que[top]=start;
   while(top>=end)
   {
       in=que[end];
       end=(end+1)0;
       for(i=0;i<4;i++)
       {
           next.x=in.x+flag[i][0];
           next.y=in.y+flag[i][1];
           if(next.x==4&&next.y==4&&map[next.x][next.y]==0)
           {
               dir[next.x][next.y].x=in.x;
               dir[next.x][next.y].y=in.y;
               return in.step+1;
           }
           if(next.x>=0&&next.x<5&&next.y>=0&&next.y<5&&map[next.x][next.y]==0)
           {
               dir[next.x][next.y].x=in.x;
               dir[next.x][next.y].y=in.y;
               map[next.x][next.y]=1;
               top=(top+1)0;
               next.step=in.step+1;
               que[top]=next;
           }
       }
   }
   return -1;

}

int main()

{
   int i,j,k,num,m,n;
   target start;
   for(i=0;i<5;i++)
       for(j=0;j<5;j++)
           scanf("%d",&map[i][j]);
   start.x=start.y=start.step=0;
   map[0][0]=1;
   num=BFS(start);
   que[0].x=4;que[0].y=4;
   k=1;i=j=4;
   while(i!=0||j!=0)
   {
       m=i;n=j;
       i=dir[m][n].x;
       j=dir[m][n].y;
       que[k].x=i;que[k++].y=j;
   }
   for(i=k-1;i>=0;i--)
       printf("(%d, %d)\n",que[i].x,que[i].y);
   return 0;

}