把严蔚敏老师这本《数据结构》再过一遍。算法这种东西时常温习一下绝对是有好处的。

#include <QCoreApplication>
#include <iostream>
#include <array>
#include <utility>
#include <stack>

//定义一个10*10的数组
std::array<std::array<int, 10>, 10> maze={
    0,0,0,0,0,0,0,0,0,0,
    0,1,0,0,0,0,1,1,0,0,
    0,1,1,1,0,0,1,0,0,0,
    0,0,0,1,1,1,1,0,0,0,
    0,0,0,0,1,0,0,0,0,0,
    0,0,0,0,1,1,1,1,1,0,
    0,0,1,0,1,0,0,0,1,0,
    0,1,1,1,1,0,0,1,1,0,
    0,0,1,0,0,0,0,0,1,0,
    0,0,0,0,0,0,0,0,0,0,
};

//这里参数不是一个引用，因为可能会涉及到修改
bool Maze(std::array<std::array<int, 10>, 10> mazeData)
{
    std::stack<std::pair<int, int>> s, sRes;
    int i = 1, j = 1;
    while (1){
        s.push(std::make_pair(i, j));
        mazeData[i][j] = 2;
        if(8 == i && 8 == j){
            break;
        }
        if(1 == mazeData[i+1][j]){
            i++;
        }else if(1 == mazeData[i][j+1]){
            j++;
        }else if(1 == mazeData[i-1][j]){
            i--;
        }else if(1 == mazeData[i][j-1]){
            j--;
        }else{
            s.pop();
            if(!s.empty()){
                i = s.top().first;
                j = s.top().second;
                s.pop();
            }else{//说明栈空了
                std::cout << "没有路径可以到达" << std::endl;
                return false;
            }
        }
    }
    //还得把它倒过来 -_- -> _-_
    while(!s.empty()){
        sRes.push(s.top());
        s.pop();
    }
    while(!sRes.empty()){
        std::cout << "(" << sRes.top().first << "," << sRes.top().second << ")" << std::endl;
        sRes.pop();
    }
    return true;
}

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    Maze(maze);
    return a.exec();
}