使用深度优先搜索算法来求解迷宫问题(C语言)

时间:2021-11-13 20:31:51

作为一名学软件的学生,现在才接触算法,实在有点……
下面是使用深度优先搜索算法的C语言代码

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

#define SIZE_OF_STACK 100 //确定栈的初始长度
#define SIZE_OF_NEW_STACK 10 //确定栈每次延展的长度
#define true 1 //个人习惯定义的类似布尔类型数据
#define false 0


//初始化迷宫,0为可走路线
int map[15][15] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};

typedef struct maze
{
int *baseX; //储存x坐标的栈底指针
int *baseY; //储存y坐标的栈底指针
int *topX; //储存x坐标的栈顶指针
int *topY; //储存y坐标的栈顶指针
int sizeStack; //储存栈的当前长度
} MAZE;

int initStack(MAZE *M); //初始化栈
int destoryStack(MAZE *M); //销毁栈
int pushStack(MAZE *M, int x, int y); //可以把坐标压入栈顶
int getTop(MAZE M, int a[2]); //获得栈顶的元素
int popStack(MAZE *M); //弹出栈顶的元素
int isEmpty(MAZE *M); //判断栈是否为空

int main()
{
MAZE M;
int tempA[2]; //定义一个用于储存坐标的数组
int x, y; //用于储存坐标的变量
int flag = 4; //标志性变量,用于每次标志已经搜索过的迷宫路径
int count; //判断每次查找到了几个方向的相同0数字
initStack(&M); //初始化栈
pushStack(&M, 1, 1); //先把迷宫入口压入栈中
while(isEmpty(&M))
{
getTop(M, tempA); //获得栈顶的元素
popStack(&M); //弹出栈顶的元素
count = 0; //每次对count初始化
if(map[tempA[0]][tempA[1]] == 0)
map[tempA[0]][tempA[1]] = flag;
//判断上下是否为0
if(tempA[0]>0 && tempA[0] < 14)
{
if(map[tempA[0]-1][tempA[1]] == 0)
{
x = tempA[0] - 1;
y = tempA[1];
pushStack(&M, x, y);
count ++;
}
else if (map[tempA[0]-1][tempA[1]] == 3)
{
break;
}
if(map[tempA[0]+1][tempA[1]] == 0)
{
x = tempA[0] + 1;
y = tempA[1];
pushStack(&M, x, y);
count ++;
}
else if (map[tempA[0]+1][tempA[1]] == 3)
{
break;
}
}
//判断左右是否为0
if(tempA[1] > 0 && tempA[1] < 14)
{
if(map[tempA[0]][tempA[1]-1] == 0)
{
x = tempA[0];
y = tempA[1] -1;
pushStack(&M, x, y);
count ++;
}
else if (map[tempA[0]][tempA[1]-1] == 3)
{
break;
}
if(map[tempA[0]][tempA[1]+1] == 0)
{
x = tempA[0];
y = tempA[1] + 1;
pushStack(&M, x, y);
count ++;
}
else if (map[tempA[0]][tempA[1]+1] == 3)
{
break;
}
}
if(1 != count)
{
flag++;
}
}

//下面开始判断哪些元素可以变成-1,用于下面的输出路径
x = y = 1;
int max = map[x][y];
int xi, yi;
while(3 != map[x][y])
{
if(x>0 && x<14)
{
if(map[x - 1][y] > max)
{
xi = x - 1;
yi = y;
max = map[xi][yi];
}
else if(map[x - 1][y] == 3)
break;
if(map[x+1][y] > max)
{
xi = x+1;
yi = y;
max = map[xi][yi];
}
else if(map[x + 1][y] == 3)
break;
if(map[x][y+1] > max)
{
xi = x;
yi = y+1;
max = map[xi][yi];
}
else if(map[x][y+1] == 3)
break;
if(map[x][y-1] > max)
{
xi = x;
yi = y-1;
max = map[xi][yi];
}
else if(map[x][y-1] == 3)
break;
}
map[xi][yi] = -1;
//下面开始进行下一轮迭代的初始化
max = 3;
x = xi;
y = yi;
}
//下面开始打印迷宫,带路线的
int i, j;
for(i=0; i<15; i++)
{
for(j=0; j<15; j++)
{
if(-1 == map[i][j])
printf("- ");
// 回复原来的值
else if(map[i][j] > 3)
printf("0 ");
else
printf("%d ", map[i][j]);
}
printf("\n");
}
destoryStack(&M);
return 0;
}

int initStack(MAZE *M)
{
M->baseX = (int *)malloc(sizeof(int) * SIZE_OF_STACK);
if(M->baseX == NULL)
{
printf("fail to get memory!\n");
exit(1);
}
M->baseY = (int *)malloc(sizeof(int) * SIZE_OF_STACK);
if(M->baseY == NULL)
{
printf("fail to get memory!\n");
exit(1);
}

M->topX = M->baseX;
M->topY = M->baseY;
M->sizeStack = SIZE_OF_STACK;
return true;
}

int destoryStack(MAZE *M)
{
free(M->baseX);
free(M->baseY);
M->topX = M->baseX = NULL;
M->topY = M->baseY = NULL;
M->sizeStack = 0;
return true;
}

int pushStack(MAZE *M, int x, int y)
{
if(M->topX - M->baseX >= M->sizeStack)
{
M->baseX = (int *)malloc(sizeof(int) * SIZE_OF_NEW_STACK);
if(M->baseX == NULL)
{
printf("fail to get memory!\n");
exit(1);
}
M->topX = M->baseX + SIZE_OF_STACK;
M->sizeStack += SIZE_OF_NEW_STACK;
}

if(M->topY - M->baseY >= M->sizeStack)
{
M->baseY = (int *)malloc(sizeof(int) * SIZE_OF_NEW_STACK);
if(M->baseY == NULL)
{
printf("fail to get memory!\n");
exit(1);
}
M->topY = M->baseY + SIZE_OF_STACK;
M->sizeStack += SIZE_OF_NEW_STACK;
}
*M->topX++ = x;
*M->topY++ = y;
return true;
}

int getTop(MAZE M, int a[2])
{
if(M.baseX == M.topX)
return false;
a[0] = *(--M.topX);
a[1] = *(--M.topY);
return true;
}

int popStack(MAZE *M)
{
if(M->baseX == M->topX)
return false;
M->topX--;
M->topY--;
return true;
}

int isEmpty(MAZE *M)
{
if(M->baseX == M->topX)
return false;
return true;
}

这里推荐一篇博客
http://blog.csdn.net/gujinjinseu/article/details/42063437