首页 > 代码库 > 搜索问题——POJ3984迷宫问题

搜索问题——POJ3984迷宫问题

2024-07-16 11:00:51   214人阅读

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)

#include<stdio.h>#include<stdlib.h>int map[5][5];int dir[4][2]={1,0,-1,0,0,1,0,-1};struct node{    int x,y;};struct node queue[50],record[5][5];void bfs(){    int i,head,tail;    struct node cur,next;    head=tail=0;    cur=queue[tail];    tail++;    while(head<tail)    {        cur=queue[head++];        for(i=0;i<4;i++)        {            next.x=cur.x+dir[i][0];            next.y=cur.y+dir[i][1];            if(next.x>=0&&next.y>=0&&next.x<5&&next.y<5&&map[next.x][next.y]==0)            {                record[next.x][next.y].x=cur.x;                record[next.x][next.y].y=cur.y;                if(next.x==4&&next.y==4)                    return ;                else                {                    map[next.x][next.y]=1;                    queue[tail++]=next;                }            }        }    }}int main(){    int i,j,k,m,n;    for(i=0;i<5;i++)    {        for(j=0;j<5;j++)            scanf("%d",&map[i][j]);    }    queue[0].x=0;    queue[0].y=0;    map[0][0]=1;    bfs();    k=0;    queue[k].x=4;    queue[k++].y=4;    i=j=4;    while(i!=0||j!=0)    {        m=i;n=j;        i=record[m][n].x;        j=record[m][n].y;        queue[k].x=i;        queue[k++].y=j;    }    for(i=k-1;i>=0;i--)    {        printf("(%d, %d)\n",queue[i].x,queue[i].y);    }    return 0;}

 


联系
我们