问题 F: DS堆栈--迷宫求解

题目描述

给出一个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 <queue>
#include <iterator>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <map>
using namespace std;

typedef struct
{
    int x;
    int y;
}position;

void test(int n)
{
    int b[n][n];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            cin>>b[i][j];
    }
    stack<position> S;
    position a,temp;
    a.x=a.y=0;
    S.push(a);
    int kk=1;
    while(!S.empty())
    {
        a=S.top();
        S.pop();
        if(S.empty())
            temp=a;
        else
            temp=S.top();
        S.push(a);
        if(a.x==n-1 && a.y==n-1)
        {
            break;
        }
        if(a.x-1>=0 && b[a.x-1][a.y]==0 && a.x-1!=temp.x)
        {
            b[a.x-1][a.y]=1;
            a.x--;

            S.push(a);
            continue;
        }
        if(a.y+1<n && b[a.x][a.y+1]==0 && a.y+1 != temp.y)
        {
            b[a.x][a.y+1]=1;
            a.y++;

            S.push(a);
            continue;
        }
        if(a.x+1<n && b[a.x+1][a.y]==0 && a.x+1!=temp.x)
        {
            b[a.x+1][a.y]=1;
            a.x++;

            S.push(a);
            continue;
        }
        if(a.y-1>=0 && b[a.x][a.y-1]==0 && a.y-1!=temp.y)
        {
            b[a.x][a.y-1]=1;
            a.y--;

            S.push(a);
            continue;
        }

        b[a.x][a.y]=1;
        S.pop();
    }
    if(!S.empty())
    {
        temp=S.top();
        stack<position> T;
        while(!S.empty())
        {
            T.push(S.top());
            S.pop();
        }
        while(!T.empty())
        {
            temp=T.top();
            cout<<'['<<temp.x<<','<<temp.y<<']'<<"--";
            if(kk==4)
            {
                cout<<endl;
                kk=1;
            }
            else
                kk++;
            T.pop();
        }
        cout<<"END"<<endl;
    }
    else
        cout<<"no path"<<endl;
}

int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        test(n);
    }
}