迷宫问题

仅代码，图解后续完善

/*
	迷宫问题
	测试用例：
	1 1 1 1 1 1
	1 0 0 1 1 1
	1 0 0 0 0 1
	1 0 1 1 1 1
	1 0 0 0 0 1
	1 1 1 1 1 1
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

#define M 4
#define N 4

typedef struct{
	int incX , incY;
}Direction;

typedef struct{
	int x , y;
	int di;
}Box;

typedef struct{
	Box box[MAX_SIZE];
	int top;
}Stack;

void InitStack(Stack &s);	//初始化 
bool isEmpty(Stack s);		//判断栈是否为空
void Push(Stack &s , Box b);		//入栈 
Box Pop(Stack &s);	//出栈
bool isFull(Stack s);		//判断栈是否为满
void display(Stack s);	//遍历 
bool findPath(int maze[][6] , Direction direct[] , Stack &s);	//寻找路径 

int main(void){
	Stack s;
	Direction direct[4];
	direct[0].incX = 0;
	direct[0].incY = 1;
	direct[1].incX = 1;
	direct[1].incY = 0;
	direct[2].incX = 0;
	direct[2].incY = -1;
	direct[3].incX = -1;
	direct[3].incY = 0;
	
	int maze[M+2][N+2];
	for(int i = 0 ; i < M+2 ; i ++){
		for(int j = 0 ; j < N+2 ; j ++){
			scanf("%d",&maze[i][j]);
		}
	}
	
	if(findPath(maze,direct,s)){
		display(s);
	}else{
		printf("迷宫没有出口！");
	}
	
	return 0;
}

void InitStack(Stack &s){
	s.top = -1;
}

bool isEmpty(Stack s){
	if(s.top == -1){
		return true;
	}else{
		return false;
	}
}

void Push(Stack &s , Box b){
	if(isEmpty(s)){
		printf("当前栈空！");
		return;
	}
	s.box[++s.top] = b;
}

bool isFull(Stack s){
	if(s.top == MAX_SIZE-1){
		return true;
	}else{
		return false;
	}
}

Box Pop(Stack &s){
	Box b;
	if(isFull(s)){
		printf("当前栈满！");
		exit(0);
	}
	b = s.box[s.top--];
	return b;
}

void display(Stack s){
	if(isEmpty(s)){
		printf("当前栈空！");
		return;
	}
	for( ; s.top > 0 ; s.top --){
		printf("(%d,%d)
",s.box[s.top].x , s.box[s.top].y);
	}
}

bool findPath(int maze[M+2][N+2] , Direction direct[4] , Stack &s){
	Box temp;
	int x , y , di;
	int line , col;
	maze[1][1] = -1;
	temp = {1,1,-1};
	Push(s,temp);
	while(!isEmpty(s)){
		temp = Pop(s);
		x = temp.x;
		y = temp.y;
		di = temp.di + 1;
		while(di < 4){
			line = x + direct[di].incX;
			col = y + direct[di].incY;
			if(maze[line][col] == 0){
				temp = {x,y,di};
				Push(s,temp);
				x = line;
				y = col;
				maze[line][col] = -1;
				if(x == M && y == N){
					return true;
				}else{
					di = 0;
				}
			}else{
				di ++;
			}
		}
	}
	return false;
}