迷宫问题非递归求解c++

迷宫问题的非递归求解通常采用广度优先搜索（Breadth-First Search, BFS）算法。在 C++ 中，可以按照以下步骤来实现：

1. 定义迷宫矩阵：首先创建一个二维数组表示迷宫，其中0代表空地，1代表墙。

2. 创建队列和起点：初始化一个队列，将起点加入队列，并设置其颜色为已访问（例如标记为白色）。

3. 主循环：在队列不为空的情况下，重复执行以下操作：
- 弹出队首节点（当前位置）
- 检查周围邻居是否是空地且未访问过：
- 如果是，将其标记为已访问（例如改变颜色），并加入队列
- 设置该位置为目标点，如果目标点找到则结束搜索

4. 判断终点：检查当前位置是否为目标点，如果是，则记录路径（回溯过程，从最后一个访问的位置开始到起点）

5. 结果输出：返回或打印一条从起点到终点的有效路径（如果存在）。

相关问题

c++求解非递归迷宫问题

以下是一个用C++解决非递归迷宫问题的示例代码：

#include <iostream>
#include <stack>
using namespace std;

// 定义迷宫的大小
const int ROW = 5;
const int COL = 5;

// 定义迷宫
int maze[ROW][COL] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0}
};

// 定义迷宫坐标结构
struct Point {
    int x;
    int y;
    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
};

// 非递归求解迷宫
bool solveMaze() {
    stack<Point> path; // 使用栈记录路径
    Point start(0, 0); // 起点坐标
    Point end(ROW - 1, COL - 1); // 终点坐标

    // 判断起点和终点是否为障碍物
    if (maze[start.x][start.y] == 1 || maze[end.x][end.y] == 1)
        return false;

    path.push(start); // 将起点入栈

    while (!path.empty()) {
        Point current = path.top();
        path.pop();

        // 判断是否到达终点
        if (current.x == end.x && current.y == end.y) {
            cout << "找到迷宫的出口!" << endl;
            return true;
        }

        // 标记当前位置为已访问
        maze[current.x][current.y] = 1;

        // 检查当前位置的四个相邻位置
        // 上方
        if (current.x - 1 >= 0 && maze[current.x - 1][current.y] == 0) {
            path.push(Point(current.x - 1, current.y));
        }
        // 下方
        if (current.x + 1 < ROW && maze[current.x + 1][current.y] == 0) {
            path.push(Point(current.x + 1, current.y));
        }
        // 左方
        if (current.y - 1 >= 0 && maze[current.x][current.y - 1] == 0) {
            path.push(Point(current.x, current.y - 1));
        }
        // 右方
        if (current.y + 1 < COL && maze[current.x][current.y + 1] == 0) {
            path.push(Point(current.x, current.y + 1));
        }
    }

    cout << "迷宫无解!" << endl;
    return false;
}

int main() {
    if (solveMaze()) {
        cout << "路径如下：" << endl;
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                cout << maze[i][j] << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

以上代码通过使用栈实现了非递归方式解决迷宫问题。迷宫使用二维数组表示，其中0表示可通过的路径，1表示障碍物。程序从起点开始，每次选择一个未访问的相邻位置，并将其入栈，直到到达终点或栈为空。如果找到了路径，则输出路径，并将迷宫中的路径位置标记为1；如果找不到路径，则输出"迷宫无解"。

c++以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 要求:首先实现一个栈类型,然后编写一个求解迷宫的非递归

实现一个栈类型：

#include<iostream>
#include<cstdlib>
using namespace std;

const int MaxSize = 100; // 栈的最大容量

template<class T>
class Stack {
public:
    Stack(); // 构造函数，初始化栈顶指针为-1
    bool isEmpty(); // 判断栈是否为空
    bool isFull(); // 判断栈是否已满
    bool push(T x); // 元素x入栈
    bool pop(T& x); // 栈顶元素出栈，并将其置于x中
    bool getTop(T& x); // 获取栈顶元素，并将其置于x中
    ~Stack(); // 析构函数
private:
    T data[MaxSize]; // 栈元素数组
    int top; // 栈顶指针
};

template<class T>
Stack<T>::Stack() {
    top = -1; // 初始化栈顶指针为-1
}

template<class T>
bool Stack<T>::isEmpty() {
    return top == -1; // 栈为空的条件是栈顶指针为-1
}

template<class T>
bool Stack<T>::isFull() {
    return top == MaxSize - 1; // 栈已满的条件是栈顶指针为MaxSize-1
}

template<class T>
bool Stack<T>::push(T x) {
    if (isFull()) return false; // 栈已满，无法入栈
    data[++top] = x; // 栈顶指针加1，将元素x入栈
    return true;
}

template<class T>
bool Stack<T>::pop(T& x) {
    if (isEmpty()) return false; // 栈为空，无法出栈
    x = data[top--]; // 将栈顶元素置于x中，栈顶指针减1
    return true;
}

template<class T>
bool Stack<T>::getTop(T& x) {
    if (isEmpty()) return false; // 栈为空，无法获取栈顶元素
    x = data[top]; // 获取栈顶元素
    return true;
}

template<class T>
Stack<T>::~Stack() { }

编写一个求解迷宫的非递归算法：

#include<iostream>
using namespace std;

const int MaxSize = 100; // 栈的最大容量
const int MaxRow = 10; // 迷宫行数的最大值
const int MaxCol = 10; // 迷宫列数的最大值

typedef struct {
    int i; // 行下标
    int j; // 列下标
    int di; // 方向
} Box;

// 根据迷宫地图生成迷宫
void generateMaze(int maze[][MaxCol], int row, int col) {
    cout << "请输入迷宫地图，0表示通路，1表示障碍：" << endl;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cin >> maze[i][j];
        }
    }
}

// 初始化迷宫路径
void initPath(int path[][MaxCol], int row, int col) {
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            path[i][j] = 0; // 初始化为0，表示未经过
        }
    }
}

// 输出迷宫地图
void printMaze(int maze[][MaxCol], int row, int col) {
    cout << "迷宫地图如下：" << endl;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cout << maze[i][j] << " ";
        }
        cout << endl;
    }
}

// 输出迷宫路径
void printPath(int path[][MaxCol], int row, int col) {
    cout << "迷宫路径如下：" << endl;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cout << path[i][j] << " ";
        }
        cout << endl;
    }
}

// 判断当前位置是否为迷宫的出口
bool isExit(Box b, int exitRow, int exitCol) {
    return b.i == exitRow && b.j == exitCol;
}

// 判断当前位置是否为迷宫的通路
bool isPath(int maze[][MaxCol], int path[][MaxCol], Box b) {
    return maze[b.i][b.j] == 0 && path[b.i][b.j] == 0;
}

// 将当前位置的四个方向压入栈中
void pushBox(Stack<Box>& s, Box b) {
    Box temp;
    temp.i = b.i - 1; // 上
    temp.j = b.j;
    temp.di = 0;
    if (temp.i >= 0) s.push(temp);
    temp.i = b.i;
    temp.j = b.j + 1; // 右
    temp.di = 1;
    if (temp.j < MaxCol) s.push(temp);
    temp.i = b.i + 1; // 下
    temp.j = b.j;
    temp.di = 2;
    if (temp.i < MaxRow) s.push(temp);
    temp.i = b.i;
    temp.j = b.j - 1; // 左
    temp.di = 3;
    if (temp.j >= 0) s.push(temp);
}

// 非递归求解迷宫
bool findPath(int maze[][MaxCol], int path[][MaxCol], int entryRow, int entryCol, int exitRow, int exitCol) {
    Stack<Box> s; // 定义栈s
    Box b;
    b.i = entryRow;
    b.j = entryCol;
    b.di = -1; // -1表示起点方向
    s.push(b); // 起点进栈
    while (!s.isEmpty()) {
        s.getTop(b); // 获取栈顶元素
        if (isExit(b, exitRow, exitCol)) { // 到达终点
            return true;
        } else if (isPath(maze, path, b)) { // 当前位置是通路
            path[b.i][b.j] = 1; // 标记当前位置已经走过
            Box temp = b; // 备份当前位置
            pushBox(s, b); // 将当前位置的四个方向压入栈中
            if (temp.i == b.i && temp.j == b.j) { // 当前位置的四个方向都没有可行的路径
                s.pop(b); // 弹出当前位置
                path[b.i][b.j] = 0; // 标记当前位置未走过
            }
        } else {
            s.pop(b); // 当前位置不是通路，弹出当前位置
        }
    }
    return false; // 没有找到通路
}

int main() {
    int maze[MaxRow][MaxCol]; // 迷宫地图
    int path[MaxRow][MaxCol]; // 迷宫路径
    int entryRow, entryCol, exitRow, exitCol; // 入口行、入口列、出口行、出口列
    cout << "请输入迷宫的行数和列数：" << endl;
    int row, col;
    cin >> row >> col;
    generateMaze(maze, row, col); // 根据迷宫地图生成迷宫
    initPath(path, row, col); // 初始化迷宫路径
    printMaze(maze, row, col); // 输出迷宫地图
    cout << "请输入迷宫的入口行、入口列、出口行、出口列：" << endl;
    cin >> entryRow >> entryCol >> exitRow >> exitCol;
    if (findPath(maze, path, entryRow, entryCol, exitRow, exitCol)) { // 求解迷宫
        printPath(path, row, col); // 输出迷宫路径
        cout << "存在通路" << endl;
    } else {
        cout << "不存在通路" << endl;
    }
    return 0;
}

输入样例：

请输入迷宫的行数和列数：
5 5
请输入迷宫地图，0表示通路，1表示障碍：
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
迷宫地图如下：
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
请输入迷宫的入口行、入口列、出口行、出口列：
0 0 4 4

输出样例：

迷宫路径如下：
1 0 0 0 0
1 0 0 0 0
1 1 1 1 1
0 0 0 0 1
0 0 0 0 1
存在通路