迷宫 C++实现

系统管理员 2022-04-22 17:48 152阅读 0赞

//文件的输入，有墙
    #include<iostream>
    #include<ctime>
    #include<cstdlib>
    #include<fstream>
    using namespace std;
    const int max1=100*100;                    //加入墙
    const int max2=102;
    bool value[max2][max2];                          //记录是否被访问过
    int maze[max2][max2];                 //迷宫的大小
    int n,m;                               //输入迷宫的长和宽
    ofstream outfile("path.txt");                                  //文件保存迷宫及输出的路径
    struct Point           //栈中的数据
    {
    	int x;
    	int y;
    };
    struct Stack
    {
    	int top;
    	Point path[max1];               //存坐标点的数组栈
    	stack()
    	{
    		top=-1;                //栈中从0开始存数据
    	}
    	bool Empty()                //检验是否为空
    	{
    		if(top==-1)return true;
    		else
    			return false;
    	}
    	void Clear()                  //清空栈
    	{
    		top=-1;
    	}
    	void Push(Point p)                   //进栈
    	{
    		top++;
    		path[top]=p;
    	}
    	Point Pop()                         //返回栈顶元素
    	{
    		return path[top]; 
    	}
    	void Delete_Pop()                         //删除顶栈元素
    	{
    		top--;
    	}
    	int Y_N_Push()
    	{
    		int x=path[top].x;
    		int y=path[top].y;
    		if(x<1||y<1||x>n||y>m||!value[x][y]||maze[x][y])        //不符合要求
    		{
    			value[x][y]=false;        //标记这个点被访问过（不能任意做标记）
    			return 1;                 
    		}
    		else
    			if((x==n)&&(y==m))               //已经找到出口，不要标记，后面直接跳出
    				return 2;
    			else
    			{
    				value[x][y]=false;        //标记这个点被访问过
    				return 3;                             //可以进栈
    			}
    	}
    	void Output()                    //输出栈中的路径
    	{
    		int i;
    		for(i=0;i<top;i++)
    		{
    			cout<<"("<<path[i].x<<","<<path[i].y<<")"<<"--->";
    		}
    		cout<<"("<<path[i].x<<","<<path[i].y<<")"<<endl;
    		outfile<<"该迷宫的路径为:"<<endl;                           //文件的输出
    		for(i=0;i<top;i++)
    		{
    			outfile<<"("<<path[i].x<<","<<path[i].y<<")"<<"--->";
    		}
    		outfile<<"("<<path[i].x<<","<<path[i].y<<")"<<endl;
    	}
    };
    Stack stack;          //不可以放在栈的定义前面
    bool Test_value()          //检验每个节点是否是否被访问过，全访问过了则为true，false为没有全部访问过
    {
    	int i,j; 
    	bool t=true;
    	for(i=1;i<=n;i++)
    		for(j=1;j<=m;j++)
    			if(value[i][j]!=false)
    			{
    				t=false;
    				break;
    			}
    		return t;
    }
    int Judge()                      
    {
    	Point t;
    	int frage=0;                            //先规定先向右
    	while(frage==0)
    	{
    		t=stack.Pop();                      //返回栈顶元素
    		t.y=t.y+1;                         //向右  
    		stack.Push(t);
    		if(stack.Y_N_Push()==1)                  //不符合要求的节点
    		{
    			stack.Delete_Pop();
    			t=stack.Pop();
    			t.x=t.x+1;           //向下
    			stack.Push(t);
    			if(stack.Y_N_Push()==1)
    			{
    				stack.Delete_Pop();
    				t=stack.Pop();
    				t.y=t.y-1;                                     //向左
    				stack.Push(t);
    				if(stack.Y_N_Push()==1)
    				{
    					stack.Delete_Pop();
    					t=stack.Pop();
    					t.x=t.x-1;								//向上
    					stack.Push(t);
    					if(stack.Y_N_Push()==1)
    					{
    						frage=4;                      //这个点4个方向都不成立
    						stack.Delete_Pop();
    					}
    				}
    			}            
    		}
    		if(stack.Y_N_Push()==2)
    		{
    			frage=5;                    //找到了出口并跳出
    			break;
    		}
    	}
    return frage;
    }
    void Search()                   
    {
    	stack.Clear();
    	Point u;
    	u.x=1;
    	u.y=1;
    	stack.Push(u);
    	value[1][1]=false;
    	while(true)
    	{
    		int t=Judge();       
    		if(t==5)                                    //找到了路
    		{
    			cout<<"找到了能通的路，路径为(用那个点的坐标表示):"<<endl;
    			stack.Output();
    			break;
    		}
    		if(t==4)stack.Delete_Pop();            //退回一个点继续找
    		if((Test_value()==true)||(stack.top==-1))                //很重要的条件，stack.top==-1，否则的话当有个点四周都不能通过的话，而且前面的点也不能通的话，就没有通路
    		{
    			cout<<"没有通路!"<<endl;
    			outfile<<"没有通路!"<<endl;
    			break;
    		}
    	}
    }
    int main()
    {
    	int i,j; 
    	cout<<"请输入迷宫的长和宽:";              //二维数组从maze[0][0]开始
    	cin>>n>>m;
    	for(i=0;i<=(m+1);i++)
    		maze[0][i]=maze[n+1][i]=1;
    	for(i=1;i<=(n+1);i++)
    		maze[i][0]=maze[i][m+1]=1;
    	cout<<"输入迷宫，1为墙，0为可通路(规定左上角为入口，右下角为出口):"<<endl;
    	srand(unsigned(time(NULL)));
    	for(i=1;i<=n;i++)
    		for(j=1;j<=m;j++)
    			maze[i][j]=(rand()%2);
    		maze[1][1]=maze[n][m]=0;
    	cout<<"输入的迷宫(带有墙)是:"<<endl;
    	for(i=0;i<=(n+1);i++)
    	{
    		for(j=0;j<=(m+1);j++)
    			cout<<maze[i][j]<<" ";
    		cout<<endl;
    	}
    	if(!outfile)
    		{
    			cerr<<"open error!"<<endl;
    			exit(1);
    		}
    	outfile<<"生成"<<n<<"行"<<m<<"列"<<"的迷宫为:"<<endl;
    	for(i=0;i<=(n+1);i++)
    	{
    		for(j=0;j<=(m+1);j++)
    			outfile<<maze[i][j]<<" ";
    		outfile<<endl;
    	}
    	for(i=1;i<=n;i++)                          //记录从value[0][0]开始
    		for(j=1;j<=m;j++)
    			value[i][j]=true;
    	Search();
    	return 0;
    }