C语言:搜索基础之迷宫问题

jlqwer 发表于 代码 分类,标签:

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 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 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>
int x[5][5];
int xi[4]={0,0,-1,1};//用来历边当前坐标的上下左右
int yi[4]={-1,1,0,0};//用来历边当前坐标的上下左右
int xr[100];//用来保存上一步的横坐标
int yr[100];//用来保存上一步的纵坐标
int pre[100];//用来保存路径的角标,pre[0]=-1作为printall的终止条件
int s=0,e=1;
void printall(int i)
{
    if(pre[i]!=-1)//直到第一个位置(0,0),这里用作终止条件,所以main里要先输出(0,0)
    {
        printall(pre[i]);//递归输出保存的路径(倒叙输出)
        printf("(%d,%d)",xr[i],yr[i]);
    }
}
void mi(int a,int b)
{
    int i;
    xr[s]=a;//保存上一步的横坐标
    yr[s]=b;//保存上一步的纵坐标
    pre[s]=-1;//保存路径的角标,pre[0]=-1作为printall的终止条件
    while(s<e)
    {
        for(i=0;i<4;i++)
        {
            a=xr[s]+xi[i];//历边当前坐标的上下左右
            b=yr[s]+yi[i];//历边当前坐标的上下左右
            if(a<0||b<0||b>=5||a>=5||x[a][b]==1)//判断是否符合条件
                continue;
            else
            {
                x[a][b]=1;
                xr[e]=a;
                yr[e]=b;
                pre[e]=s;//保存符合条件的路径
                e++;//最后位置++
            }
            if(a==4&&b==4)//寻完结束
                printall(s);
        }
        s++;//路径前移
    }
}
int main()
{
    int i,j;
    for(i=0;i<5;i++)
        for(j=0;j<5;j++)
        scanf("%d",&x[i][j]);
    printf("(0,0)");
    mi(0,0);
    printf("(4,4)");
    return 0;
}