迷宫问题.cpp

都是自己编写的常用算法的事例,本人础作. 里面有:哈密尔顿环,皇后问题,图的着色问题,子集和数问题,树和等价问题,栈的各种用发等.

//Begin of file 迷宫问题.cpp
#include "SqStack.h"
//栈的基本数据类型
#define MazeSize 4
//迷宫的规模
void main()
{	
//求迷宫中从入口到出口的所有简单路径，用一个二维数组表示迷宫。
//这是一个经典的程序设计问题，所用的是借助栈的回溯法。
	SqStack S;InitStack(S);         //工作栈的声明和初始化
	SElemType e;                    //活动结点
    void visit(SElemType );         //visit子函数的声明，用于最后输出求出 的路径

	                                //输入迷宫。
    SElemType Maze[MazeSize][MazeSize];
	for(int i=0;i<MazeSize;i++)
		for(int j=0;j<MazeSize;j++){
			Maze[i][j].x=i;
			Maze[i][j].y=j;
			Maze[i][j].visited=0;
			cout<<"请输入坐标为("<<i<<","<<j<<")是否是障碍物"<<endl;
			cin>>Maze[i][j].obstruct;
		}//for	

                                   // 迷宫输出
	for(i=0;i<MazeSize;i++){
		for(int j=0;j<MazeSize;j++)
			cout<<Maze[i][j].obstruct;
         cout<<endl;
	}//for

                                  //迷宫问题的求解
	Push(S,Maze[0][0]);  Maze[0][0].visited=1;

	while(!StackEmpty(S)){
            GetTop(S,e);
                    			//是否还存在可通的（右，下方向）相临的顶点
			if(e.y+1<MazeSize&&!Maze[e.x][e.y+1].visited&&!Maze[e.x][e.y+1].obstruct){//右相临可通
				Push(S,Maze[e.x][e.y+1]);
				Maze[e.x][e.y+1].visited=1;
				if(e.x==MazeSize-1&&e.y+1==MazeSize-1) {
					cout<<"路径已经找到"<<endl;
					break;
				}//if
			}//if
			else if(e.x+1<MazeSize&&!Maze[e.x+1][e.y].visited&&!Maze[e.x+1][e.y].obstruct){//下相临可通
                Push(S,Maze[e.x+1][e.y]);
				Maze[e.x+1][e.y].visited=1;
				if(e.x+1==MazeSize-1&&e.y==MazeSize-1){
                      		cout<<"路径已经找到"<<endl;

					break;
				}//if
			}//else if
            else                //不存在可通的（右，下方向）相临的顶点
				Pop(S,e);	
	}//while
	
	
	if(StackEmpty(S)) 
			cout<<"不存在可同的路径"<<endl;
	else
            StackTraverse(S,visit);
                       
}//main

void visit(SElemType h){
	cout<<"( "<<h.x<<","<<h.y<<")"<<endl;
}