|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
用了说找不到这个头文件，但是这不是c++自带的吗
#include "Stack.h"
#include <iostream>
#include <stdlib.h> //exit函数要用到
using namespace std;
struct Box //将每个迷宫格子看成是一个结构体
{
int x, y, di;
//x和y分别代表迷宫格子的横纵坐标，di为当前的方向
};
struct Direction //构建结构体
{
int incX, incY;
};
typedef struct Node //这是栈节点
{
Box data;
struct Node* pNext;
}Node, *PNODE;
class Stack
{
private:
PNODE pTop;
PNODE pBottom;
public:
Stack();
void initStack(Stack*);
void pushStack(Stack*, Box);
//将栈中的栈底元素返回并移除，用递归来实现栈逆序遍历的
Box getElement(Stack&, Box&);
void reverse(Stack&, Box&);
void traverse(Stack*);
void pop(Stack*, Box&);
bool isEmpty(Stack*);
};
Stack::Stack()
{
//ctor
}
void Stack::initStack(Stack* pS)
{
pS->pTop = new Node;
if(nullptr == pS->pTop){
cout << "动态内存分配失败！" << endl;
exit(-1);
}
else{
pS->pBottom = pS->pTop;
pS->pTop->pNext = nullptr;
}
return;
}
void Stack::pushStack(Stack* pS, Box temp) //temp是将一个结构体整体入栈
{
PNODE pNew = new Node;
pNew->data = temp;
pNew->pNext = pS->pTop;
pS->pTop = pNew;
}
/** 这里开始是逆序遍历栈的关键代码，等会详细讲解 */
Box Stack::getElement(Stack& s, Box& temp)
{
s.pop(&s, temp);
Box res = temp;
if(s.isEmpty(&s)) return res;
else{
Box last = getElement(s, temp);
s.pushStack(&s, res);
return last;
}
}
void Stack::reverse(Stack& s, Box& temp)
{
if(s.isEmpty(&s)) return;
Box i = getElement(s, temp);
s.reverse(s, temp);
s.pushStack(&s, i);
}
/****************************************/
void Stack::traverse(Stack* pS)
{
PNODE p = pS->pTop; //p是移动指针，在栈顶和栈底间上下移动的
while(p != pS->pBottom)
{
cout << "(" << p->data.x << ", " << p->data.y << ")" << endl;
p = p->pNext;
}
cout << endl;
return;
}
void Stack::pop(Stack* pS, Box& temp) //这里的temp一定要 采用引用
{
if(isEmpty(pS)) return;
else{
PNODE r = pS->pTop;
temp = r->data;
pS->pTop = r->pNext;
free(r);
r = NULL;
return;
}
}
bool Stack::isEmpty(Stack* pS)
{
if(pS->pTop == pS->pBottom)
return true;
else
return false;
}
bool findPath(Stack& s, int M, int N)
{
int **maze = new int*[M+2]; //动态构造二维数组
for(int i = 0; i < 10; i++){
maze[i] = new int[N+2];
}
for(int i = 0; i < M+2; i++){ //动态给定迷宫
for(int j = 0; j < N+2; j++){
if(i == 0 || i == M+1)
maze[i][j] = 1;
else if(j == 0 || j == N+1)
maze[i][j] = 1;
else
cin >> maze[i][j];
}
}
Direction direct[4]; //方向数组（文章上面有图有说到）
direct[0].incX = 0; direct[0].incY = 1;
direct[1].incX = 1; direct[1].incY = 0;
direct[2].incX = 0; direct[2].incY = -1;
direct[3].incX = -1; direct[3].incY = 0;
Box temp;
int x, y, di; //当前正在处理的迷宫格子
int line, col; //迷宫格子预移方向后，下一格子的行坐标、列坐标
maze[1][1] = -1;
temp.x = 1;
temp.y = 1;
temp.di = -1; //起始点直接设置为-1代表该格子已访问过了
s.pushStack(&s, temp);
while(!s.isEmpty(&s))
{
s.pop(&s, temp); //这里对遇到走不通的格子进行回退时起到关键作用
x = temp.x; y = temp.y; di = temp.di+1;
while(di < 4){ //走不通时，四个方向都尝试一遍
line = x + direct[di].incX;
col = y + direct[di].incY;
if(maze[line][col] == 0){ //代表 预走 的格子可以走
temp.x = x; temp.y = y; temp.di = di;
s.pushStack(&s, temp);
x = line; y = col; maze[line][col] = -1; //标为-1是为了表明该格子已经走过，回溯时不再处理
if(x == M && y == N){
s.reverse(s, temp);
return true; //迷宫有路
}
else di = 0;
}
else di++;
}
}
return false; //迷宫无路
}
int main()
{
int M, N;
bool res;
cout << "请输入迷宫数组行数和列数：";
cin >> M >> N;
Stack s;
s.initStack(&s);
res = findPath(s, M, N);
cout << boolalpha << res << endl; //将bool转换为true/false显示
cout << endl;
if(res)
s.traverse(&s);
else
cout << "你被困在迷宫中了，等着受死吧！" << endl;
return 0;
}
从你的代码中，我看到你自己实现了一个栈，而没有使用C++标准模板库(STL)中的 std::stack 。如果你想使用STL中的栈，你需要包含 <stack> 头文件，并使用 std::stack 。下面是一个使用STL中的 std::stack 的简化版代码： #include <iostream>#include <stack>#include <vector>using namespace std;struct Box { int x, y, di;};struct Direction { int incX, incY;};bool findPath(stack<Box>& s, int M, int N, const vector<vector<int>>& maze) { Direction direct[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; int x, y, di; vector<vector<int>> visited = maze; visited[1][1] = -1; s.push({1, 1, -1}); while (!s.empty()) { Box temp = s.top(); s.pop(); x = temp.x; y = temp.y; di = temp.di + 1; while (di < 4) { int line = x + direct[di].incX; int col = y + direct[di].incY; if (visited[line][col] == 0) { s.push({x, y, di}); x = line; y = col; visited[line][col] = -1; if (x == M && y == N) { return true; } else { di = 0; } } else { di++; } } } return false;}int main() { int M, N; cout << "请输入迷宫数组行数和列数："; cin >> M >> N; vector<vector<int>> maze(M + 2, vector<int>(N + 2, 1)); for (int i = 1; i <= M; ++i) { for (int j = 1; j <= N; ++j) { cin >> maze[i][j]; } } stack<Box> s; bool res = findPath(s, M, N, maze); cout << boolalpha << res << endl; if (res) { while (!s.empty()) { Box temp = s.top(); s.pop(); cout << "(" << temp.x << ", " << temp.y << ")" << endl; } } else { cout << "你被困在迷宫中了，等着受死吧！" << endl; } return 0;}
请注意，我已经删除了你自定义的栈类，并用 std::stack 替换了它。同时，我还将原来的二维数组替换为 vector<vector<int>> ，这是一个更现代且易于使用的数据结构。
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-7-7 15:05:47
置顶卡
千斤顶
显身卡
发表于 2023-7-7 15:07:00
楼主
