|
1.分析
路用蓝色块表示：0 墙用红色块表示：1 选定一个入口，人从入口进去，把走过的路标记为1（视为红色，不能再去走），走过的路径用栈stack[++top]保存起来。 如图中人的地方，往右边不能走，就把路径出栈stack[top--]，回到人原来的地方，并且把它右边标记为1.人再次走的时候就会选择下方去走 
2.上代码，我们一个一个来看
3.首先的来一个迷宫吧，申请一个二维数组便且随机初始化我们的迷宫
int**make_array(int rows, int cols)
{
int**array = (int**)malloc(sizeof(int*)*rows);
for (int i = 0; i
printf("请输入迷宫大小:");
scanf("%d", &size);
maze = make_array(size + 2, size + 2);
//周围搞一圈数字“1”的墙
for (int i = 0; i
for (int j = 1; j
switch (rand() % 8)
{
case 0:
case 1:
maze[i][j] = 1;
break;
default:
maze[i][j] = 0;
break;
}
}
printf("%d\t", maze[i][j]);
}
printf("\n\n");
}
}
4.有了迷宫就需要去寻路
int find_path()
{
//4个方向的位移变化
POSITION offset[4];
//以右边顺时针开始
offset[0].x = 0;//右边
offset[0].y = 1;
offset[1].x = 1;//下
offset[1].y = 0;
offset[2].x = 0;//左边
offset[2].y = -1;
offset[3].x = -1;//up
offset[3].y = 0;
//路口选定为：迷宫左上角
// ....0可走，1为墙....
POSITION here = { 1,1 };
//....走过的地方给它堵住...
maze[1][1] = 1;
int option = 0;//从右边顺时针往左
int last_option = 3;
while (here.x != size || here.y != size)
{
int row, col;//记录下标的变化
while (option
path_stack[++stack_top] = here;
here.x = row;
here.y = col;
maze[row][col] = 1;
option = 0;//下一个位置依旧从右边试探
}
//不能走应该怎么办？
else
{
if (stack_top == -1)
{
return 0;
}
//退回上一步位置，一直不能走就一直退
POSITION next = path_stack[stack_top];
stack_top--;
option = 0;
here = next;
}
}
return 1;
}
5.打印你的路径
#if 0
void print_path()
{
printf("路径:\n");
POSITION here;
while (stack_top != -1)
{
here = path_stack[stack_top--];
printf("(%d,%d) ", here.x, here.y);
}
printf("(%d,%d)", size, size);
printf("\n");
}
#else
void print_path()
{
printf("路径:\n");
for (int i = 0; i
srand((unsigned int)time(0));
create_map();
if (find_path())
{
print_path();
}
else
{
printf("此迷宫没有出口");
}
return 0;
}
7.效果演示
确确实实有这样一条路 
8.不能走情况方向的优化
 优化代码：
if (next.x == here.x)
{
option = 2 + next.y - here.y;
}
else
{
option = 3 + next.x - here.x;
}
|