迷宫问题

Time Limit:1000MS		Memory Limit:65536K
Total Submissions:3850		Accepted:2226

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

0 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0

Sample Output

(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4)

总结：用队列来实现广搜，如果有输出方向的要求，可以用last_dir[][]记录但因该注意栈溢出的问题。

code:

#include
      
        #include
       
         int dx[4]={-1,0,0,1},dy[4]={
    0,-1,1,0}; int q[100000]; int maze[5][5]; int vis[5][5]; int dist[5][5]; int fa[5][5]; void bfs(int x,int y) {    int front=0,rear=0,d,u;        u=x*5+y;        vis[x][y]=1;                                         dist[x][y]=0;        q[rear++]=u;        fa[x][y]=u;    while(front
        
         =0&&nx<5&&ny>=0&&ny<5&&!maze[nx][ny]&&!vis[nx][ny])                        {                int v=nx*5+ny;                                q[rear++]=v;                                vis[nx][ny]=1;                                fa[nx][ny]=u;    //保存新格子(nx,ny)父亲编号                    dist[nx][ny]=dist[x][y]+1;             //last_dir[nx][ny]=d;                      //保存父亲节点到他的移动方向                       }                }        } } void print_path(int x,int y) {    int fx=fa[x][y]/5;    int fy=fa[x][y]%5;    if(fx!=x||fy!=y)        {                printf("(%d, %d)\n",fx,fy);                print_path(fx,fy);      //putchar(name[last_dir[x][y]]);        } } int main() {    int i,j;            memset(maze,0,sizeof(maze));            memset(vis,0,sizeof(vis));            memset(dist,0,sizeof(dist));            memset(q,0,sizeof(q));        for(i=0;i<5;i++)            for(j=0;j<5;j++)                            scanf("%d",&maze[i][j]);                    bfs(4,4);                printf("(0, 0)\n");                print_path(0,0);    return 0; }
        
       
      

补充： void print_path(int x,int y) {    int fx=fa[x][y]/5;    int fy=fa[x][y]%5;    if(fx!=x||fy!=y)        {                printf("(%d, %d)\n",fx,fy);                print_path(fx,fy);        } }   //用到了递归的技巧：如果格子(x,y)有父亲(fx,fy),打印之。非递归形式：

int dir[maxn*maxn]; void print_path(int x,int y) {    int c=0;    for(;;)        {        int fx=fa[x][y]/m;        int fy=fa[x][y]%m;        if(fx==x&&fy==y)            break;                dir[c++]=last_dir[x][y];                x=fx;                y=fy;    }   while(c--)                putchar(name[dir[c]]); }