DS堆栈--迷宫求解

本文主要是介绍DS堆栈--迷宫求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题 B: 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
 

 注意图示的隐藏案例，第一个格子为1的时候直接no path！！

 代码实现：

#include <iostream>
#include <stack>
using namespace std;struct position {int x;int y;
};class Maze {int** maze;int size;stack<position> path;
public:Maze(int n);int  Go();
};
Maze::Maze(int n) {size = n;maze = new int* [n];for (int i = 0; i < n; i++)maze[i] = new int[n];for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> maze[i][j];
}int Maze::Go() {if (maze[0][0] == 1) //直接no path 并且跳出函数{cout << "no path" << endl;return 0;}// 进入迷宫path.push({ 0, 0 });maze[0][0] = 1;int i = 0, j = 0;// 迷宫按照右下左上走while (true) {if (path.empty() || (i == size - 1 && j == size - 1))  //如果回退到起点或者到达终点就结束循环break;if (j + 1 < size && maze[i][j + 1] == 0)    //向右{maze[i][j + 1] = 1;   //代表走过path.push({ i, ++j }); //走到 i,j+1位置，入栈}else if (i + 1 < size && maze[i + 1][j] == 0)    //向下{maze[i + 1][j] = 1;path.push({ ++i, j });}else if (j - 1 >= 0 && maze[i][j - 1] == 0)  //向左{maze[i][j - 1] = 1;path.push({ i, --j });}else if (i - 1 >= 0 && maze[i - 1][j] == 0)  //向上{maze[i - 1][j] = 1;path.push({ --i, j });}else    //无路可走{//回退i = path.top().x;j = path.top().y;//判断回退之后是否还有可以走的路if (!((j + 1 < size && maze[i][j + 1] == 0) || (i + 1 < size && maze[i + 1][j] == 0) || (j - 1 >= 0 && maze[i][j - 1] == 0) || (i - 1 >= 0 && maze[i - 1][j] == 0)))path.pop();  //出栈}}//输出路径if (!path.empty()){stack<position> path1;while (!path.empty())   //将path倒序{path1.push(path.top());path.pop();}i = 0;while (!path1.empty()) {if ((++i) % 4 == 0)cout << '[' << path1.top().x << ',' << path1.top().y << ']' << "--" << endl;elsecout << '[' << path1.top().x << ',' << path1.top().y << ']' << "--";path1.pop();}cout << "END" << endl;}else cout << "no path" << endl;return 0;
}
int main() {int t;cin >> t;while (t--) {int n;cin >> n;Maze myMaze(n);myMaze.Go();}return 0;
}

日常提神醒脑环节：

 

 

 

这篇关于DS堆栈--迷宫求解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---