DS堆栈--迷宫求解-布布扣-bubuko.com

题目描述

给出一个N*N的迷宫矩阵示意图，从起点[0,0]出发，寻找路径到达终点[N-1, N-1]

要求使用堆栈对象来实现，具体算法参考课本3.2.4节51页

输入

第一行输入t，表示有t个迷宫

第二行输入n，表示第一个迷宫有n行n列

第三行起，输入迷宫每一行的每个方格的状态，0表示可通过，1表示不可通过

输入n行

以此类推输入下一个迷宫

输出

逐个输出迷宫的路径

如果迷宫不存在路径，则输出no path并回车

如果迷宫存在路径，将路径中每个方格的x和y坐标输出，从起点到终点，每输出四个方格就换行，最终以单词END结尾，具体格式参考示范数据

输出的代码参考如下：

//path是保存路径的堆栈，堆栈中每个元素都包含x坐标和y坐标，用属性xp和yp表示

//path1是一个临时堆栈，把path的数据倒序输出到path1，使得路径按正序输出

if (!path.empty()) //找到路径

{ //......若干代码，实现path的数据导入path1

i=0; //以下是输出路径的代码

while (!path1.empty())

{ cpos = path1.top();

if ( (++i)%4 == 0 )

cout<<‘[‘<<cpos.xp<<‘,‘<<cpos.yp<<‘]‘<<"--"<<endl;

else

cout<<‘[‘<<cpos.xp<<‘,‘<<cpos.yp<<‘]‘<<"--";

path1.pop();

}

cout<<"END"<<endl;

}

else

cout<<"no path"<<endl; //找不到路径输出no path

样例输入

2 8 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 0 7 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0

样例输出

[0,0]--[0,1]--[0,2]--[1,2]-- [1,3]--[2,3]--[3,3]--[3,4]-- [4,4]--[5,4]--[5,5]--[6,5]-- [6,6]--[7,6]--[7,7]--END no path

提示

#include<iostream>
#include<stack>
using namespace std;
const int maxx=100;
int maze[maxx][maxx];
int n;///迷宫为n行n列
int direction(int i,int j)///i,j为当前位置，direction判断四个方向中按照右下左上优先级哪个方向可行
{
    if(j+1<n&&maze[i][j+1]==0)
        return 1;
    else if(i+1<n&&maze[i+1][j]==0)
        return 2;
    else if(j-1>=0&&maze[i][j-1]==0)
        return 3;
    else if(i-1>=0&&maze[i-1][j]==0)
        return 4;
    return 0;
}
int main()
{
    int T;
    cin>>T;
    int Fx[5]={0,0,1,0,-1};
    int Fy[5]={0,1,0,-1,0};
    ///右下坐标系
    while(T--)
    {
        cin>>n;
        stack<int>pathx;
        stack<int>pathy;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>maze[i][j];
        pathx.push(0);
        pathy.push(0);
        maze[0][0]=1;
        int i=0,j=0;
        while(1)
        {
            int d=direction(i,j);
            if(d!=0)
            {
                i+=Fx[d];
                j+=Fy[d];
                maze[i][j]=1;
                pathx.push(i);
                pathy.push(j);
                if(i==n-1&&j==n-1)///走通了
                    break;
            }
            else if(d==0)
            {
                pathx.pop();
                pathy.pop();
                i=pathx.top();
                j=pathy.top();///回溯
                if(i==0&&j==0)///走回去了
                    break;
            }
        }
        if(i==0&&j==0)
        {
            cout<<"no path"<<endl;
        }
        else
        {
            stack<int>path1x;
            stack<int>path1y;
            while(!pathx.empty())
            {
                path1x.push(pathx.top());
                pathx.pop();
            }
            while(!pathy.empty())
            {
                path1y.push(pathy.top());
                pathy.pop();
            }
            int tag=0;
            while(!path1x.empty()&&!path1y.empty())
            {
                if((++tag)%4==0)
                    cout<<"["<<path1x.top()<<","<<path1y.top()<<"]"<<"--"<<endl;
                else
                    cout<<"["<<path1x.top()<<","<<path1y.top()<<"]"<<"--";
                path1x.pop();
                path1y.pop();
            }
            cout<<"END"<<endl;
        }
    }
    return 0;
}

DS堆栈--迷宫求解

原文：https://www.cnblogs.com/SZU-DS-wys/p/12177989.html