maze.cpp

数据结构经典算法的C语言实现 计算机专业数据结构课程实验

#include<iostream.h>
         
const int MAX = 100;

enum Boolean{FALSE, TRUE};
struct  stack {                  
    int elements[MAX];          
    int top;                    
};  //定义栈类型

//清空栈
void MAKENULL(stack &s) {
	s.top = 0;
}
//判断栈是否为空
Boolean EMPTY(stack s) {
	if(s.top < 1)
		return TRUE;
	else
		return FALSE;
}
//取栈顶元素
int TOP(stack s) {
	if(EMPTY(s)) {
        cout<<"栈空";
		return NULL;
	}
	else
		return (s.elements[s.top]);
}
//出栈
int POP(stack &s) {
	if(EMPTY(s)) {
		cout<<"栈空";
		return NULL;
	}
	else {
		s.top = s.top - 1;
		return s.elements[s.top + 1];
	}
}
//进栈
void PUSH(int x,stack &s) {
	if(s.top == MAX - 1)
		cout<<"栈满";
	else {
		s.top = s.top + 1;
		s.elements[s.top] = x;
	}
}

int flag[MAX][MAX];          //全局量，访问标记数组
//非递归求解函数
int GETMAZE1(int a[][MAX], int move[][3], int s) {
	int i = 1, j = 1, v = 1, g = 0, h = 0;
	stack c;

	MAKENULL(c);
    if(a[1][1] == 1) {
		cout<<"此迷宫无解！"<<endl;
		return 0;
	}
	if(s == 1) {
		cout<<"路径是(1,1)"<<endl;
		return 1;
	}
	do {
		g = i + move[v][1];
		h = j + move[v][2];
		if((g == s)&&(h == s)&&(a[s][s] == 0)) {
			cout<<"走出迷宫的路径是："<<endl;
			PUSH(i, c);
			PUSH(j, c);
			PUSH(v, c);
			cout<<"("<<s<<","<<s<<")"<<"<-";
			while(!EMPTY(c)) {
				POP(c);
				j = TOP(c);
				POP(c);
				i = TOP(c);
				POP(c);
				cout<<"("<<i<<","<<j<<")"<<"<-";
				}
			cout<<"出发点"<<endl;
			return 1;
		}
		if((a[g][h] == 0)&&(flag[g][h] == 0)) {
			flag[g][h] = 1;
			PUSH(i, c);
			PUSH(j, c);
			PUSH(v, c);
			i = g;
			j = h;
			v = 1;
		}
		else if(v < 8) {
			v = v + 1;
		}
		else {
			while((v == 8)&&(!EMPTY(c))) {
				v = TOP(c);
				POP(c);
				j = TOP(c);
				POP(c);
                i = TOP(c);
				POP(c);
			}
			v++;
		}
		
	} while(v != 9);
	cout<<"此迷宫无解！"<<endl;
	return 0;
}
//递归求解函数
int GETMAZE2(int a[][MAX], int move[][3], int s, int x, int y) {
	int i;
	int g, h;
	if((x == s)&&(y == s))
		return 1;
	for(i=1;i<9;i++) {
		g = x + move[i][1];
		h = y + move[i][2];
		if((a[g][h] == 0)&&(flag[g][h]) == 0) {
			flag[g][h] = 1;
			if(GETMAZE2(a, move, s, g, h) == 1) {
				cout<<"("<<g<<","<<h<<")<-";
				return 1;
			}
		}
	}
	if((x == 1)&&(y == 1))
		cout<<"此迷宫无解！"<<endl;
	return 0;
}

void main() {
label1:
	int a[MAX][MAX], move[9][3];      
	int i, j = 1, k = 1, u = 0, h = 0, q;
	char yn;
	
	cout<<"程序功能：一个M*M迷宫矩阵，本程序可以求出从其左上角到右下角的通路。"<<endl<<endl;
	cout<<"请输入迷宫的大小，即M*M矩阵的M值：";
	cin>>i;
	
	//初始化走步方位数组
	move[1][1] = move[3][2] = move[5][1] = move[7][2] = 0;
	move[1][2] = move[2][1] = move[2][2] = move[3][1] = move[4][1] = move[8][2] = 1;
	move[4][2] = move[5][2] = move[6][2] = move[6][1] = move[7][1] = move[8][1] = -1;
    q = i + 2;
	
	//初始化访问标记数组
    while(u < q) {
		while(h < q) {
			flag[u][h] = 0;
			h++;
		}
		u++;
		h = 0;
	}
    flag[1][1] = 1;
	
	//迷宫数组的输入，边界设置障碍
	u = 0;
	while(u <= i) {
		a[0][u] = 1;
		u++;
	}
	u = 1;
	while(u <= i) {
		a[u][0] = 1;
		u++;
	}
	u = 0;
	while(u <= i+1) {
		a[i+1][u] = 1;
		u++;
	}
	u = 0;
	while(u <= i) {
		a[u][i+1] = 1;
		u++;
	}

	cout<<"矩阵中0表示能够通过，1表示不能通过。"<<endl;
	while(j <= i) {
		while(k <= i) {
			cout<<"("<<j<<","<<k<<")能否通过：";
			cin>>a[j][k];
			k++;
		}
		k = 1;
		j++;
	}

label2:	
	cout<<"请选择：1.递归求解    2.非递归求解"<<endl;
	cin>>k;
	
	if(k == 1) {    	//调用递归函数求解
        if(a[1][1] == 1)     
			cout<<"此迷宫无解！"<<endl;
		else if(i == 1)
			cout<<"路径是(1,1)"<<endl;
		else {
			cout<<"走出迷宫的路径是："<<endl;	
			if(GETMAZE2(a, move, i, 1, 1) == 1) {
				cout<<"(1,1)<-出发点"<<endl;
			}
		}
	}
	else if(k == 2)	    //调用非递归函数求解
		GETMAZE1(a, move, i);
	else {
		cout<<"输入错误！请重新选择！"<<endl;
		goto label2;
	}
	
	cout<<"是否继续？继续请选y，退出请选n："<<endl;     
	cin>>yn;
	if(yn == 'y' || yn == 'Y')
		goto label1;
}