迷宫找路径，只要找到了一条就跳出

亦凉 2022-05-15 03:38 118阅读 0赞

#include<iostream>
    using namespace std;
    
    int n;int Maze[101][101];
    
    bool vis[101][101];
    
    struct unit//栈中的单元，记录x，y坐标
    {
    	int x,y;
    };
    
    struct list
    {
    	int top;//栈顶指针
    	unit place[101*101];
    
    	list(){top=0;}
    
    	bool back()//判断是否可入栈
    	{
    		int x = place[top-1].x;int y=place[top-1].y;
    		if(x<1||y<1||x>n||y>n||vis[y][x]||Maze[y][x] != 0)
    			return false;
    		return true;
    	}
    
    	void push(unit u)
    	{place[top++] = u;}
    
    	void pop()
    	{--top;}
    
    	unit get()//返回栈顶元素
    	{return place[top-1];}
    
    	bool empty()//判断是否为空
    	{
    		if(top==0)
    			return true;
    		return false;
    	}
    
    	void clear()//清空栈
    	{top=0;}
    
    	bool judge()
    	{
    		if(place[top-1].x==n&&place[top-1].y==n)
    			return true;
    		return false;
    	}
    }stack;
    
    void main()
    {
    //	int n;
    	while(cin>>n)
    	{
    		stack.clear();
    		bool flag = false;
    		memset(Maze,1,sizeof(Maze));
    		memset(vis,0,sizeof(vis));
    		for(int i=1;i!=n+1;i++)
    			for(int j=1;j!=n+1;j++)
    				cin>>Maze[i][j];
    		unit u,u1;u.x =1;u.y =1;stack.push(u);//起点入栈
    		vis[1][1] = true;
    		while(!stack.empty())
    		{
    			u = stack.get();
    			if(stack.judge())//判断是否找到目标
    			{
    				flag = true;
    				cout<<"find it"<<endl;break;
    			}
    			stack.pop();//出栈
    			u1 = u;//向右搜索
    			u1.x+=1;
    			stack.push(u1);//入栈
    			if(!stack.back())//判断是否符合标准（是否出界，是否访问过等）
    				stack.pop();//若不符合，出栈
    			else//反之
    				vis[u1.y] [u1.x] = true;//标记为访问过
    			u1 = u;//向左搜索
    			u1.x-=1;
    			stack.push(u1);
    			if(!stack.back())
    				stack.pop();
    			else
    				vis[u1.y] [u1.x] = true;
    			u1 = u;//向上搜索
    			u1.y+=1;
    			stack.push(u1);
    			if(!stack.back())
    				stack.pop();
    			else
    				vis[u1.y] [u1.x] = true;
    			u1 = u;//向下搜索
    			u1.y-=1;
    			stack.push(u1);
    			if(!stack.back())
    				stack.pop();
    			else
    				vis[u1.y] [u1.x] = true;
    		}
    		if(flag == false)
    			cout<<"can't reach"<<endl;
    
    	}
    }

输入的数据：

4 //矩阵的大小  
0 1 1 0  
0 0 1 1  
1 0 1 1  
0 0 0 0