C语言重解经典回溯算法案例-迷宫问题
C语言重解经典回溯算法案例-迷宫问题
迷宫问题是一道经典的回溯算法问题，给定一个迷宫矩阵，矩阵中的1表示障碍，0表示可走通路，给定迷宫入口出口，要求寻找从入口穿过迷宫到达出口的所有路径，有则输出，无则给出提示。一本合格的数据结构教科书一般都会介绍迷宫问题，网上的分析也是铺天盖地，这里就不再赘述重复的内容了。废话不多说，简单介绍一下程序，然后上代码。
该程序用二维数组表示迷宫，用另一个二维数组记录迷宫中的位置是否已经走过，同时用一个链式栈存放搜索出的临时路径。程序从迷宫入口开始试探，随着回溯试探过程的进行，链式栈的长度不断变化，当试探到迷宫出口时，链表中存放的就是一条完整的穿过迷宫的路径了，输出路径后回溯，继续试探下一条路径，当回溯到入口时没有新的可走方向时整个回溯试探的过程也就结束了。链表节点中除了存放被路径连接的各单元的行列标外，还存放有由该节点代表的单元前往该节点的后继节点代表的单元的方向，这么做是为了方便回溯操作的进行。
为方便起见，程序中迷宫的入口是固定的，为左上角单元，出口同样固定，为右下角单元。这并不妨碍程序的普适性，只要稍加修改就可以使程序适用于任意给定的出口和入口的情形。
啰嗦了这么半天，下面该上代码了，代码用C语言编写，具体如下。
#include <stdio.h>
#include <malloc.h>
void convert(int *i, int *j, int k); //将当前单元行标列标i,j更新为方向k所指向的相邻单元的行标列标
int boundary(int i, int j, int d, int n, int m); //检查(i,j)单元在d方向上是否为迷宫边界,是返回0，不是返回1
int barrier(int i, int j, int d, int **p); //检查(i,j)单元在d方向上是否遇到障碍，是返回0，不是返回1
int visit(int i, int j, int d, int **t); //检查(i,j)单元在d方向上的相邻单元是否已走过，是返回0，不是返回1
int direction(int i, int j, int d, int n, int m, int **p, int **t); //检查(i,j)单元在d方向上是否可走,可走返回1，否则返回0
int trial(int i, int j, int k, int n, int m, int **p, int **t); //在(i,j)单元上从k方向的下一个方向起寻找下一个可走方向,找到返回方向号，否则返回0
void main ()
{
int i, j, k; //i,j为单元位置标识,k为方向参数
int m, n; //m为迷宫行数,n为迷宫列数
int flag, Num; //flag标志是否存在走出迷宫的路径,Num为找到的路径序号
int min, max;
char *q;
int **p, **t; //p指向表示迷宫的二维数组,t指向记录迷宫中的每个位置是否已走过的二维数组
struct Record //表示路径节点的结构体类型
{
int x;
int y; //节点对应单元的行列标
int sign;
int mark; //记录当前节点的后继节点对应的单元相对于当前节点对应的单元的方向
struct Record *next;
struct Record *before;
};
struct Record *head, *psnewbe, *psnewaf, *current;
typedef struct Record Record1;
struct Long
{
int Num;
int length;
struct Long *next;
};
struct Long *head1, *psnew1, *p1;
typedef struct Long Long1;
printf ("please input the number of row and col of the Maze matrix\n");
printf ("please enter the row\n");
printf ("row=");
scanf ("%d", &m); //输入迷宫矩阵行列数
printf ("please enter the col\n");
printf ("col=");
scanf ("%d", &n);
q=(char *) malloc((n+1)*sizeof(char));
p=(int **) malloc(m*sizeof(int *));
for (i=0; i<m; i++)
{
p[i]=(int *) malloc(n*sizeof(int));
printf("please input the %dnd row of Maze matrix\n", i+1); //初始化迷宫矩阵,0表示可走,1表示障碍
scanf ("%s", q);
for (j=0; j<n; j++)
*(p[i]+j)=q[j]-48;
}
t=(int **) malloc(m*sizeof(int *));
for (i=0; i<m; i++)
{
t[i]=(int *) malloc(n*sizeof(int)); //初始化标志迷宫矩阵每一位置是否已走过的矩阵
for (j=0; j<n; j++)
*(t[i]+j)=0;
}
head=(Record1 *) malloc(sizeof(Record1));
psnewbe=head;
psnewaf=head; //初始化双向链表栈
head->next=NULL;
head->before=NULL;
head1=(Long1 *) malloc(sizeof(Long1));
head1->next=NULL;
psnew1=head1;
flag=0; //初始化标志是否存在走出迷宫路径的标志变量
Num=0;
i=0;
j=0; //初始化当前单元行列标,将迷宫左上角单元作为出发点
k=0; //方向参数初始化为0,对左上角单元从头开始试探可走方向
loop: if (trial(i, j, k, n, m, p, t)==0) //回溯试探开始
{
if (i==0&&j==0) //在起始点已无方向可走,回溯结束
{
goto exit;
}
else
{
if (k==0) //(i,j)元的所有方向均不可走,回溯
{
i=psnewaf->x;
j=psnewaf->y;
k=psnewaf->mark;
goto loop;
}
else //在(i,j)元上沿k方向后的所有方向均不可走,回溯
{
*(t[i]+j)=0;
free (psnewaf);
psnewbe->next=NULL;
psnewaf=psnewbe; //(i,j)元节点弹出栈
psnewbe=psnewbe->before;
i=psnewaf->x;
j=psnewaf->y;
k=psnewaf->mark;
goto loop;
}
}
}
else
{
if (k==0) //从头开始为(i,j)元找到了可走方向trial(i, j, k, n, m, p, t)
{
current=(Record1 *) malloc(sizeof(Record1));
current->x=i;
current->y=j; //建立(i,j)元节点
current->mark=trial(i, j, k, n, m, p, t);
if (i==0&&j==0)
{
current->sign=1;
}
else
{
current->sign=psnewaf->sign+1;
}
current->next=NULL;
psnewaf->next=current;
current->before=psnewaf; //(i,j)元作为节点压入栈
psnewbe=psnewaf;
psnewaf=current;
*(t[i]+j)=1; //(i,j)元标志为已走
}
else //从k方向的下一方向开始为(i,j)元找到了可走方向trial(i, j, k, n, m, p, t)
{
psnewaf->mark=trial(i, j, k, n, m, p, t); //相应更新(i,j)元节点中的方向
}
convert(&i, &j, trial(i, j, k, n, m, p, t)); //沿找到的方向从(i,j)元递进至下一单元
k=0; //为为下一单元从头开始寻找新方向作准备
if (i==(m-1)&&j==(n-1)) //抵达迷宫出口
{
flag=1; //标志变量置1
current=(Record1 *) malloc(sizeof(Record1));
current->x=i;
current->y=j;
current->sign=psnewaf->sign+1; //建立并压入代表迷宫出口的尾节点
current->next=NULL;
psnewaf->next=current;
current->before=psnewaf;
Num++; //找到路径数增1
printf("\nThe %dnd possible route:\n", Num); //输出路径序号
current=head->next;
while (current!=NULL)
{
if (current->next!=NULL)
{
printf ("(%d,%d)->", current->x+1, current->y+1); //输出找到的路径
}
else
{
printf ("(%d,%d) ", current->x+1, current->y+1);
printf ("long %d", current->sign);
p1=(Long1 *) malloc(sizeof(Long1));
p1->Num=Num;
p1->length=current->sign;
p1->next=NULL;
psnew1->next=p1;
psnew1=p1;
if (Num==1)
{
min=current->sign;
max=current->sign;
}
else
{
if (current->sign<min)
min=current->sign;
if (current->sign>max)
max=current->sign;
}
}
current=current->next;
}
printf ("\n");
current=psnewaf->next;
free (current); //尾节点弹出栈
psnewaf->next=NULL;
i=psnewaf->x;
j=psnewaf->y; //回溯
k=psnewaf->mark;
}
goto loop;
}
exit: ;
if (flag==0)
{
printf ("There is no possible route\n");
}
else
{
printf ("There are %d routes in total\n", Num);
printf ("The length of shortest route is %d shortest routes include:\n", min);
psnew1=head1->next;
while (psnew1!=NULL)
{
if (psnew1->length==min)
printf ("The %dnd route\n", psnew1->Num);
psnew1=psnew1->next;
}
printf ("The length of longest route is %d longest routes include:\n", max);
psnew1=head1->next;
while (psnew1!=NULL)
{
if (psnew1->length==max)
printf ("The %dnd route\n", psnew1->Num);
psnew1=psnew1->next;
}
}
}
void convert(int *i, int *j, int k)
{
int *p1, *p2;
p1=i;
p2=j;
if (k==1)
{
*p1=*p1-1;
}
else
{
if (k==2)
{
*p1=*p1-1;
*p2=*p2+1;
}
else
{
if (k==3)
{
*p2=*p2+1;
}
else
{
if (k==4)
{
*p1=*p1+1;
*p2=*p2+1;
}
else
{
if (k==5)
{
*p1=*p1+1;
}
else
{
if (k==6)
{
*p1=*p1+1;
*p2=*p2-1;
}
else
{
if (k==7)
{
*p2=*p2-1;
}
else
{
*p1=*p1-1;
*p2=*p2-1;
}
}
}
}
}
}
}
}
int boundary(int i, int j, int d, int n, int m)
{
if (i==0||i==m-1||j==0||j==n-1)
{
if (i==0&&j!=0)
{
if (j!=n-1)
{
if (m==1)
{
if (d==8||d==1||d==2||d==6||d==5||d==4)
return (0);
else
return (1);
}
else
{
if (d==8||d==1||d==2)
return (0);
else
return (1);
}
}
else
{
if (m==1)
{
if (d==8||d==1||d==2||d==3||d==4||d==5||d==6)
return (0);
else
return (1);
}
else
{
if (n==1)
{
if (d==8||d==1||d==2||d==3||d==4||d==6||d==7)
return (0);
else
return (1);
}
else
{
if (d==8||d==1||d==2||d==3||d==4)
return (0);
else
return (1);
}
}
}
}
else
{
if (j==n-1&&i!=0)
{
if (i!=m-1)
{
if (n==1)
{
if (d==8||d==2||d==3||d==4||d==6||d==7)
return (0);
else
return (1);
}
else
{
if (d==2||d==3||d==4)
return (0);
else
return (1);
}
}
else
{
if (m==1)
{
if (d==8||d==1||d==2||d==3||d==4||d==5||d==6)
return (0);
else
return (1);
}
else
{
if (n==1)
{
if (d==8||d==2||d==3||d==4||d==5||d==6||d==7)
return (0);
else
return (1);
}
else
{
if (d==2||d==3||d==4||d==5||d==6)
return (0);
else
return (1);
}
}
}
}
else
{
if (i==m-1&&j!=n-1)
{
if (j!=0)
{
if (m==1)
{
if (d==8||d==1||d==2||d==4||d==5||d==6)
return (0);
else
return (1);
}
else
{
if (d==4||d==5||d==6)
return (0);
else
return (1);
}
}
else
{
if (m==1)
{
if (d==8||d==1||d==2||d==4||d==5||d==6||d==7)
return (0);
else
return (1);
}
else
{
if (n==1)
{
if (d==8||d==2||d==3||d==4||d==5||d==6||d==7)
return (0);
else
return (1);
}
else
{
if (d==8||d==4||d==5||d==6||d==7)
return (0);
else
return (1);
}
}
}
}
else
{
if (i!=0)
{
if (n==1)
{
if (d==8||d==2||d==3||d==4||d==6||d==7)
return (0);
else
return (1);
}
else
{
if (d==6||d==7||d==8)
return (0);
else
return (1);
}
}
else
{
if (m==1)
{
if (d==8||d==1||d==2||d==4||d==5||d==6||d==7)
return (0);
else
return (1);
}
else
{
if (n==1)
{
if (d==8||d==1||d==2||d==3||d==4||d==6||d==7)
return (0);
else
return (1);
}
else
{
if (d==8||d==1||d==2||d==6||d==7)
return (0);
else
return (1);
}
}
}
}
}
}
}
else
{
return (1);
}
}
int barrier(int i, int j, int d, int **p)
{
int m, n;
m=i;
n=j;
convert (&m, &n, d);
if (*(p[m]+n)==0)
return (1);
else
return (0);
}
int visit(int i, int j, int d, int **t)
{
int m, n;
m=i;
n=j;
convert (&m, &n, d);
if (*(t[m]+n)==0)
return (1);
else
return (0);
}
int direction(int i, int j, int d, int n, int m, int **p, int **t)
{
if (boundary(i, j, d, n, m)==0) //(i,j)元在d方向为边界
{
return (0); //d方向不可走
}
else
{
if (barrier(i, j, d, p)==0) //(i,j)元在d方向遇到障碍
{
return (0); //d方向不可走
}
else
{
if (visit(i, j, d, t)==0) //(i,j)元在d方向上的相邻单元已经走过
return (0); //d方向不可走
else
return (1); //d方向可走
}
}
}
int trial(int i, int j, int k, int n, int m, int **p, int **t)
{
int q;
q=k;
for (q++; q<=8; q++) //从k方向的下一方向开始寻找从(i,j)元可走的方向
{
if (direction(i, j, q, n, m, p, t)==1)
return (q); //找到可走方向，将其返回
}
return (0); //没有可走方向，返回0
}
评论暂时关闭