Question

求c++迷宫问题的代码

要求：求出所有的路径，我想用dfs，但不知道所有路径怎么求。当一个点无法走通时，这个点出栈，但是当前栈顶元素，又不能走这个以出栈的点，而当前栈顶的这个点的其他3个方向（能走的通的话）的点，却可以走到这个点去。这个用具体的代码如何去实现呢，求代码。

Answer 1

#include <vector>
#include <iostream>
#include <ctime>
#include <string>
#include <cassert>
#include <stack>
#include <limits>
typedef std::string row_t;
typedef std::vector<row_t> maze_t;
char const SPACE = ' ', OBSTACLE = '*', LEFT = '<', UP = '^', RIGHT = '>', DOWN = 'V';
maze_t generate_maze(size_t const row, size_t const column) {
    static bool inited;
    if (!inited) {// 初始化随机数
        srand(static_cast<unsigned>(time(0)));
        inited = true;
    }
    maze_t maze(row + 2, row_t(column + 2, OBSTACLE));
    for (size_t i = 1; i <= row; ++i) {
        for (size_t j = 1; j <= column; ++j) {
            if (rand() % 3 != 0) maze[i][j] = SPACE;
        }
    }
    maze[1][0] = maze[1][1] = maze[row][column + 1] = SPACE;// 出入口
    return maze;
}
template<typename OStream>
OStream& operator<<(OStream &ostr, maze_t const &maze) {
    for (size_t i = 0; i != maze.size(); ++i) {
        ostr << maze[i] << "\n";
    }
    return ostr;
}
bool find_path(maze_t &maze) {
    assert(maze[1][1] != OBSTACLE);
    typedef std::vector<size_t> tag_row;
    size_t const MAX = std::numeric_limits<size_t>::max(), row = maze.size(), column = maze.front().size();
    std::vector<tag_row> tags(row, tag_row(column, MAX));
    struct position_t {
        size_t r, c;
    };
    // 进行标记
    std::stack<position_t> s;
    tags[1][0] = 0;
    tags[1][1] = 1;
    position_t pos = { 1, 1 };
    s.push(pos);
    while (!s.empty()) {
        pos = s.top(); s.pop();
        size_t const next_step = tags[pos.r][pos.c] + 1;
        if (pos.r > 1 && tags[pos.r - 1][pos.c] > next_step && maze[pos.r - 1][pos.c] != OBSTACLE) {
            position_t tmp = { pos.r - 1, pos.c };
            tags[tmp.r][tmp.c] = next_step;
            s.push(tmp);
        }
        if (pos.c > 1 && tags[pos.r][pos.c - 1] > next_step && maze[pos.r][pos.c - 1] != OBSTACLE) {
            position_t tmp = { pos.r, pos.c - 1 };
            tags[tmp.r][tmp.c] = next_step;
            s.push(tmp);
        }
        if (pos.r < row - 2 && tags[pos.r + 1][pos.c] > next_step && maze[pos.r + 1][pos.c] != OBSTACLE) {
            position_t tmp = { pos.r + 1, pos.c };
            tags[tmp.r][tmp.c] = next_step;
            s.push(tmp);
        }
        if (pos.c < column - 2 && tags[pos.r][pos.c + 1] > next_step && maze[pos.r][pos.c + 1] != OBSTACLE) {
            position_t tmp = { pos.r, pos.c + 1 };
            tags[tmp.r][tmp.c] = next_step;
            s.push(tmp);
        }
    }
    pos = { row - 2, column - 2 };
    size_t step = tags[pos.r][pos.c];
    if (step == MAX) return false;// 没有通路
    // 寻找最短通路
    maze[1][0] = maze[1][1] = maze[row - 2][column - 1] = RIGHT;
    while (step != 1) {// 还没有回到起点
        // 寻找step最小的邻居
        position_t tmp;
        if (pos.r > 1 && tags[pos.r - 1][pos.c] < step) {
            tmp.r = pos.r - 1; tmp.c = pos.c;
            step = tags[tmp.r][tmp.c];
            maze[pos.r][pos.c] = DOWN;
        }
        if (pos.c > 1 && tags[pos.r][pos.c - 1] < step) {
            tmp.r = pos.r ; tmp.c = pos.c - 1;
            step = tags[tmp.r][tmp.c];
            maze[pos.r][pos.c] = RIGHT;
        }
        if (pos.r < row - 2 && tags[pos.r + 1][pos.c] < step) {
            tmp.r = pos.r + 1; tmp.c = pos.c;
            step = tags[tmp.r][tmp.c];
            maze[pos.r][pos.c] = UP;
        }
        if (pos.c < column - 2 && tags[pos.r][pos.c + 1]  < step) {
            tmp.r = pos.r; tmp.c = pos.c + 1;
            step = tags[tmp.r][tmp.c];
            maze[pos.r][pos.c] = LEFT;
        }
        pos = tmp;
    }
    return true;
}
int main() {
    size_t const m = 23, n = 77;
    maze_t maze, path;
    do {
        path = maze = generate_maze(m, n);
    } while (find_path(path) == false);
    std::cout << maze << "\n" << path << "\n";
    return 0;
}

上面是迷宫，下面是找到的通路。入口在左上角，出口在右下角。