从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可以到达,则到达新点,否则试探下一方向;若该点所有的方向均没有通路,则沿原路返回前一个点,换下一个方向再继续试探,直到所有可能的通路都探索到,再找到下一条通路,或无路可走又退回到入口点。
退回到的“前一点”正是刚刚被访问过的,具有“后进前出”的特性,需要用栈保存所能够到达的每一点的下标及从该点前进的方向。
用二维数组maze[M+2][N+2]来表示迷宫,图中红色的部分为迷宫,而迷宫的四周的值全部为1(即不通)。这样设计的话,将迷宫中所有点都演变成迷宫中部的某点,可以保证无论那个点的试探方向都是四个。
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
typedef struct{
//x,y方向上的增量
int incX,intcY;
}Direction;
Direction direct[4];
/*
从某点(x,y)按某一方向
v(0<=v<=3)到达的新点
(line,col)的坐标:
*/
line =x + direct[v].intcX;
col = y + direct[v].intcY;
direct[0].intcX = 0;
direct[0].intcY = 1;
direct[1].intcX = 1;
direct[1].intcY = 0;
direct[2].intcX = 0;
direct[2].intcY = -1;
direct[3].intcX = -1;
direct[3].intcY = 0;
栈中元素是一个由行、列、方向组成的三元组;
typedef struct{
int x,y;//当前访问的迷宫格子的纵横坐标
int di;//当前方向
}Box;
另外设置一标志数组flag[m][n],其所有元素都初始化为0,一旦到达了某点(i,j)之后,将对应flag[i][j]置1,下次再试探该位置时,因为已经置1了,就不能再选它了;
当到达某点(i,j)后将对应maze[i][j]置-1,其他未到达过的点其值只能是1或0,可与未到达过的点区分开来。
bool findpath(int maze[M+2][N+2],Direction direct[],Stack &s){
Box temp;
int x,y,di;//迷宫格子当前处理单元的纵横坐标和方向
int line,col;//迷宫数组下一单元的行坐标和列坐标
maze[1][1]=-1;
temp={1,1,-1};
s.push(temp);
while(!s.isEmpty()){//栈不为空
temp = s.pop();
x=temp.x;y=temp.y;di=temp.di+1;
while(di<4){//方向未尝试完
line = x + direct[di].intcX;
col = y + direct[di].intcY;
if(maze[line][col]==0){
temp = {x,y,di};
s.push(temp);
x=line;y=col;maze[line][col]=-1;
if(x==M && y==N) return true;//迷宫有路
else di=0;
}
else di=0;
}
}
return false;//迷宫没有路
}
//栈中存的是一条迷宫通路
基本要求:
? 编写非递归程序求解。
? 迷宫存储在文件中,通过输入文件名(in.* ),
创建相应的迷宫。迷宫文件的格式自己设计。
? 最终的解要求在屏幕上显示并存入文件(out.*)中。
解的显示方式以及解文件的格式自己设计。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 100
#define li 10
#define colum 10
typedef struct {
int elem[MAXSIZE][3];
int top;
} Stack;
// 判断栈是否为空
int Empty(Stack *s) {
if (s->top == -1)
return 1;
else
return 0;
}
// 入栈操作
int Push(Stack *s, int x[3]) {
if (s->top == MAXSIZE - 1)
return 0;
else {
s->top++;
s->elem[s->top][0] = x[0];
s->elem[s->top][1] = x[1];
s->elem[s->top][2] = x[2];
return 1;
}
}
// 出栈操作
int Pop(Stack *s) {
if (Empty(s))
return 0;
else {
s->top--;
return 1;
}
}
// 寻找迷宫路径
_Bool findPath(int maze[li][colum], Stack *s) {
int temp[3];
int x, y, di;
int line, col;
int direct[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
maze[1][1] = -1;
temp[0] = 1;
temp[1] = 1;
temp[2] = -1;
Push(s, temp);
while (!Empty(s)) {
Pop(s);
temp[0] = s->elem[s->top + 1][0];
temp[1] = s->elem[s->top + 1][1];
temp[2] = s->elem[s->top + 1][2];
x = temp[0];
y = temp[1];
di = temp[2] + 1;
while (di < 4) {
line = x + direct[di][0];
col = y + direct[di][1];
if (maze[line][col] == 0) {
temp[0] = x;
temp[1] = y;
temp[2] = di;
Push(s, temp);
x = line;
y = col;
maze[line][col] = -1;
if (x == 8 && y == 8)
return true;
else
di = 0;
} else
di++;
}
}
return false;
}
// 打印栈中元素
void print(Stack *s) {
for (int i = 0; i <= s->top; i++) {
printf("(%d,%d) ", s->elem[i][0], s->elem[i][1]);
if ((i + 1) % 4 == 0)
printf("\n");
}
}
// 打印迷宫
void Print(int maze[li][colum]) {
for (int i = 0; i < li; i++) {
for (int j = 0; j < colum; j++) {
printf("%2d", maze[i][j]);
if (j % 10 == 9) {
printf("\n");
}
}
}
}
// 将迷宫保存到文件
void saveMazeToFile(int maze[li][colum], const char *filename) {
FILE *file = fopen(filename, "w");
if (file == NULL) {
fprintf(stderr, "Error opening file: %s\n", filename);
exit(EXIT_FAILURE);
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
fprintf(file, "%d ", maze[i][j]);
}
fprintf(file, "\n");
}
fclose(file);
}
// 将解保存到文件
void saveSolutionToFile(Stack *s, const char *filename) {
FILE *file = fopen(filename, "w");
if (file == NULL) {
fprintf(stderr, "Error opening file: %s\n", filename);
exit(EXIT_FAILURE);
}
for (int i = 0; i <= s->top; i++) {
fprintf(file, "(%d,%d) ", s->elem[i][0], s->elem[i][1]);
if ((i + 1) % 4 == 0)
fprintf(file, "\n");
}
fclose(file);
}
int main() {
int maze[li][colum] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
{1, 0, 1, 0, 1, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1, 0, 0, 1},
{1, 0, 0, 0, 1, 0, 1, 0, 0, 1},
{1, 1, 1, 1, 1, 0, 1, 0, 1, 1},
{1, 0, 0, 0, 1, 0, 1, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};
Stack s;
s.top = -1;
saveMazeToFile(maze, "in.txt");
if (findPath(maze, &s)) {
printf("Maze:\n");
Print(maze);
printf("\nSolution:\n");
print(&s);
saveSolutionToFile(&s, "out.txt");
} else {
printf("No path\n");
}
return 0;
}
???????