迷宫问题求解

迷宫问题（控制台）——数据结构

preface: 本项目是求解迷宫问题，主要为对数据结构中——顺序栈的应用

 代码如下：我这里不作多解释，只作记录

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:4996)
//#pragma execution_character_set("utf-8")
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

#define ERROR 0;
#define OK 1;

#define Map_col 10
#define Map_row 10
// 1：障碍
// 2： 路径
// 0：空地
// -1: 标记为空地不可走。

#define MAXSIZE 100
#define SIZEADD 10
typedef struct {
	int y; // 行
	int x; // 列
}ElemType;

typedef struct {
	ElemType* top;
	ElemType* base;
	int stacksize;
}SqStack;

void init_map(int choice, int map[][Map_col]);
void show_map(int map[][Map_col]);
void init_stack(SqStack& T);
int Get_top_elem(SqStack T, ElemType& e);
int choose_direction(int map[][Map_col], SqStack T, ElemType& out);
void push_stack(SqStack& T, int map[][Map_col], ElemType e);
void pop_stack(SqStack& T, int map[][Map_col], ElemType& e);
int if_win(const SqStack T);
void solve_path(SqStack& T, int map[][Map_col]);
void clear_stack(SqStack& T);
void destroy_stack(SqStack& T);

int main()
{
	SqStack T;			//用顺序栈储存 要走过的格子的坐标
	init_stack(T);
	int map[Map_col][Map_row];


	while (TRUE) {
		char buffer[4];
		int choice;
		fputs("\n请选择关卡(1,2,3), -1退出。\n: ", stdout);
		fgets(buffer, 3, stdin);
		choice =(int)strtol(buffer,NULL ,10);
		if (choice == -1) {
			fputs("\n游戏结束，再见！！", stdout);
			break;
		}
		else if (choice == 1 || choice == 2 || choice == 3) {
			init_map(choice, map);
			show_map(map);
			solve_path(T, map);
		}
		else fputs("输入不合法", stdout);
	}

    return 0;
}
void solve_path(SqStack &T,int map[][Map_col]) {
	ElemType e;
	e.x = 1;
	e.y = 1;
	push_stack(T, map,e);// 先入起点
	//map[e.y][e.x] = 2;
	
	ElemType in;
	ElemType out;

	while (TRUE) {
		if (if_win(T) == 1) {
			fputs("解答成功！！\n", stdout);
			show_map(map);
			break;
		}
		else if(if_win(T) == -1)
		{
			fputs("\n本关卡无解！！请更换有效地图\n", stdout);
			break;
		}
		if (choose_direction(map, T, in)) {
			push_stack(T, map, in);
		//	map[in.y][in.x] = 2;
		}
		else {
			pop_stack(T,map, out);
		//	map[out.y][out.x] = -1;
		}
		//fputs("\n", stdout);
		//Sleep(1000);
		//show_map(map);
	}
	clear_stack(T);
}
int if_win(const SqStack T) {
	if (T.base == T.top) return -1;//游戏无解
	ElemType now = *(T.top-1);

	if (now.x == Map_col - 2 && now.y == Map_row - 2) {
		return 1;	//找到路径
	}
	else return 0;  //还未找到
}
void destroy_stack(SqStack& T) {
	if (T.base != NULL) { // 检查栈是否已初始化
		free(T.base); // 释放栈底内存
		T.base = NULL;
		T.top = NULL;
		T.stacksize = 0;
	}
}
void clear_stack(SqStack& T) {
	if (T.base != NULL) {
		T.top = T.base;
	}
}
//入栈
void push_stack(SqStack& T,int map[][Map_col], ElemType e) {
	if (T.top - T.base >= T.stacksize) {
		T.base = (ElemType*)realloc(T.base, 
			(T.stacksize + SIZEADD) * sizeof(ElemType));
		if (!T.base) {
			perror("malloc");
			exit(-1);
		}
			T.top = T.base + T.stacksize;
			T.stacksize += SIZEADD;
	}
	*T.top++ = e;
	map[e.y][e.x] = 2;
}
void pop_stack(SqStack& T,int map[][Map_col], ElemType &e) {
	if (T.base == T.top) exit(-1);
	e = * --T.top;
	map[e.y][e.x] = -1;
}
int choose_direction(int map[][Map_col], SqStack T, ElemType &out) {
	ElemType now_pos;
	ElemType round_pos[4];
	Get_top_elem(T,now_pos);
	//  定位 上下左右 四个格子
	round_pos[0].x = now_pos.x;
	round_pos[0].y = now_pos.y - 1;
	round_pos[1].x = now_pos.x - 1;
	round_pos[1].y = now_pos.y;
	round_pos[2].x = now_pos.x + 1;
	round_pos[2].y = now_pos.y;
	round_pos[3].x = now_pos.x;
	round_pos[3].y = now_pos.y + 1;
	
	int j = 0;
	ElemType chose[4];
	for (int i = 0; i < 4; i++) {		//计算这个格子四周有多少个可走格子
		if (map[round_pos[i].y][round_pos[i].x] == 0) {
			chose[j].x = round_pos[i].x;
			chose[j].y = round_pos[i].y;
			j++;
		}
	}
	if (j == 0) {
		return 0; //表示 该出栈了。
	}
	else {
		srand(time(NULL));
		int temp = rand() % j;
		out = chose[temp];
		return 1;
	}
}
int Get_top_elem(SqStack T, ElemType &e) {
	if (T.base == T.top) return ERROR;
	e = *(T.top - 1);
	return OK;
}
void init_stack(SqStack& T) {
	T.top = (ElemType*)malloc(MAXSIZE*sizeof(ElemType)); 
	T.base = T.top;
	//T.top = T.top + 1;
	T.stacksize = MAXSIZE;
}
void show_map(int map[][Map_col]) {
	for (int i = 0; i < Map_row; i++) {
		for (int j = 0; j < Map_col; j++) {
			switch (map[i][j])
			{
			case -1:
			case 0: fputs("  ", stdout);
				break;
			case 1: fputs(" ■", stdout);
				break;
			case 2: fputs(" *", stdout);
				break;
			default:
				break;
			}
		}
		fputs("\n", stdout);
	}

}
void init_map(int choice, int map[][Map_col]) {
	FILE* fp;
	fp = NULL;
	switch (choice)
	{
		case 1: fp = fopen("./map//Le1.txt", "r");
			break;
		case 2: fp = fopen("./map/Le2.txt", "r");
			break;
		case 3: fp = fopen("./map/Le3.txt", "r");
			break;
				//fp = fopen("./map/Le3.txt", "r");
	default:
		break;
	}

	if (!fp) {
		perror("fopen");
		exit(-1);
	}

	for (int i = 0; i < Map_row; i++) {
		for (int j = 0; j < Map_col; j++) {
			fscanf(fp, "%d", &map[i][j]);
		}
	}	
	fclose(fp);
	fp = NULL;
}