C语言迷宫求解——栈的应用

程序运行结果:

C语言迷宫求解——栈的应用

算法思想及程序实现:

  1. 求迷宫路径算法的基本思想:若当前位置“可通”,则纳入路径,继续前进;
    若当前位置“不可通”,则后退,换方向继续探索; 若四周“均无通路”,则将当前位置从路径中删除出去。
  2. 定义相关结构体:
 //迷宫中的坐标位置
typedef struct {
	int x;//行号
	int y;//列号
} PosType;

//栈的元素类型
typedef struct {
	PosType seat;//通道块在迷宫中的“坐标位置”
	int direction;//从此通道块走向下一通道块的方向,di=1,2,3,4分别表示东,南,西,北
} SElemType;

typedef struct SqStack {
	SElemType data[MAXSIZE];
	int top;//指向栈顶元素
} SqStack;
  1. 通过二维数组定义迷宫,并设置起点和终点坐标,(' '表示通道块,'#'表示墙壁,在后面的执行过程中,迷宫的元素可能变成'*'表示路径,'@'表示曾经走过但是无法到达出口):
//定义迷宫,' '表示通道块,'#'表示墙壁,在后面的执行过程中,迷宫的元素可能变成'*'表示路径,'@'表示曾经走过但是无法到达出口
static char maze[mazeRowNum][mazeRowNum] = {
	{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
	{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
	{'#', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#'},
	{'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
	{'#', ' ', '#', '#', '#', ' ', '#', ' ', '#', '#'},
	{'#', ' ', ' ', ' ', '#', ' ', '#', ' ', '#', '#'},
	{'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
	{'#', '#', '#', '#', '#', ' ', '#', '#', ' ', '#'},
	{'#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
	{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};

PosType start = {1, 1};//设置迷宫起点
PosType end = {8, 8};//设置迷宫终点
  1. 对曾经走过的通道块留下痕迹,以防止所求路径不是简单路径:
void footPrint(PosType curpos) {
	maze[curpos.x][curpos.y] = '*';//表示到达了该通道块
}
  1. 曾走过的通道块但是无法到达出口,是“不通的”路,标记以免陷入“死胡同”:
void markPrint(PosType curpos) {
	maze[curpos.x][curpos.y] = '@';//表示该通道块虽然不是墙壁,但是它仍然不通
}
  1. 定义函数实现从当前位置“行走”到下一个位置:
PosType nextPos(PosType curpos, int direction) {
	switch(direction) {
		case 1:
			curpos.y++;
			break;//向东走,行号不变,列号加1
		case 2:
			curpos.x++;
			break;//向南走,行号加1,列号不变
		case 3:
			curpos.y--;
			break;//向西走,行号不变,列号减1
		case 4:
			curpos.x--;
			break;//向北走,行号减1,列号不变
	}
	return curpos;
}
  1. 判断当前位置是否可通,即为' ',而不是'#'、'*'(已走过)、'@'(已走过但不通):
bool pass(PosType curpos) {
	if(maze[curpos.x][curpos.y] == ' ')
		return true;
	else
		return false;
}
  1. 若迷宫中存在从入口start到出口end的通道,则求得一条路径存放在栈中(从栈底到栈顶),并返回TRUE,否则返回FALSE:
bool mazePath(PosType start, PosType end) {
	SqStack s;
	initStack(s);
	PosType curpos = start;//设定当前位置为“入口”位置
	//int curstep = 0;  //探索的第一步,用于表示路径序号
	do {
		if(pass(curpos)) { //当前路径可通(是未曾到达过的通道块)
			footPrint(curpos);//留下"到此一游"的标记,为了求得的路径是简单路径
			//SElemType e = {curpos, 1};
			SElemType e;
			e.seat = curpos;
			e.direction = 1;
			push(s, e);  //加入路径
			if(curpos.x == end.x && curpos.y == end.y)  //到达出口
				return true;
			curpos = nextPos(curpos, 1);//下一位置是当前位置的东边
			//curstep++;   //探索下一步
		} else { //当前位置不能通过,则栈顶元素出栈,因为栈顶位置是当前位置的“来向”通道块,即当前位置的前一个位置
			SElemType e;
			pop(s, e);
			//如果弹出的栈顶位置的四周均不可通,则继续往“来路”通道块回退
			while(e.direction == 4 && !isEmpty(s)) {
				markPrint(e.seat);//标记此通道块已经走过且不可通,标记是为了避免陷入死胡同
				pop(s, e);
			}
			//弹出的栈顶位置尚有其他方向的方块未探索,则切换到下一个方向的方块为当前位置
			if(e.direction < 4) {
				e.direction++;
				push(s, e);
				curpos = nextPos(e.seat, e.direction);
			}
		}//end else
	} while(!isEmpty(s));//栈不为空则循环继续
	return false;
}
  1. 定义函数打印迷宫:
//打印迷宫
void printMaze() {
	for(int i = 0; i < mazeRowNum; i++) {
		for(int j = 0; j < mazeColNum; j++) {
			printf("%c ", maze[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
//仅打印迷宫中的路径
void printPath() {
	for(int i = 0; i < mazeRowNum; i++) {
		for(int j = 0; j < mazeColNum; j++) {
			if(i == 0 || j == 0 || i == mazeRowNum-1 || j == mazeColNum-1 || maze[i][j] == '*') {
				printf("%c ", maze[i][j]);
			} else {
				printf("  ");
			}
		}
		printf("\n");
	}
	printf("\n");
}
//仅打印迷宫中的路径坐标 
void printPathOrder() {
	for(int i = 0; i < mazeRowNum; i++) {
		for(int j = 0; j < mazeColNum; j++) {
			if( maze[i][j] == '*') {
				printf("(%d,%d) ", i,j);
			}
		}
	}
	printf("\n");
}
  1. 主函数
int main() {
	printf("迷宫的初始状态:\n");
	printMaze();
	if(mazePath(start, end)) {
		printf("存在通路!\n\n");
		printf("路径坐标:\n");
		printPathOrder();
		printf("\n迷宫的现态:\n");
		printMaze();
		printf("迷宫里的路径:\n");
		printPath();
	} else
		printf("不存在通路!\n");
	return 0;
}
上一篇:文件实时同步后防篡改的操作记录


下一篇:app 跳转小程序