回溯算法经典问题-迷宫问题

迷宫问题是一道经典的回溯算法问题，给定一个迷宫矩阵，矩阵中的1表示障碍，0表示可走通路，给定迷宫入口出口，要求寻找从入口穿过迷宫到达出口的所有路径，有则输出，无则给出提示。一本合格的数据结构教科书一般都会介绍迷宫问题，网上的分析也是铺天盖地，这里就不再赘述重复的内容了。废话不多说，简单介绍一下程序，然后上代码。

    该程序用二维数组表示迷宫，用另一个二维数组记录迷宫中的位置是否已经走过，同时用一个链式栈存放搜索出的临时路径。程序从迷宫入口开始试探，随着回溯试探过程的进行，链式栈的长度不断变化，当试探到迷宫出口时，链表中存放的就是一条完整的穿过迷宫的路径了，输出路径后回溯，继续试探下一条路径，当回溯到入口时没有新的可走方向时整个回溯试探的过程也就结束了。链表节点中除了存放被路径连接的各单元的行列标外，还存放有由该节点代表的单元前往该节点的后继节点代表的单元的方向，这么做是为了方便回溯操作的进行。

   为方便起见，程序中迷宫的入口是固定的，为左上角单元，出口同样固定，为右下角单元。这并不妨碍程序的普适性，只要稍加修改就可以使程序适用于任意给定的出口和入口的情形。

  啰嗦了这么半天，下面该上代码了，代码用C++语言编写，具体如下。

#include 
#include 
#include 
using namespace std;
void convert(size_t& i, size_t& j, unsigned short k);  //将当前单元行标列标i,j更新为方向k所指向的相邻单元的行标列标
bool boundary(const size_t& i, const size_t& j, unsigned short d, const size_t& n, const size_t& m);  //检查(i,j)单元在d方向上是否为迷宫边界,是返回0，不是返回1
bool barrier(const size_t& m, const size_t& n, const vector>& p);  //检查(i,j)单元在d方向上是否遇到障碍，是返回0，不是返回1
bool visit(const size_t& m, const size_t& n, const vector>& t);    //检查(i,j)单元在d方向上的相邻单元是否已走过，是返回0，不是返回1
bool direction(const size_t& i, const size_t& j, unsigned short d, const size_t& n, const size_t& m, const vector>& p, const vector>& t);   //检查(i,j)单元在d方向上是否可走,可走返回1，否则返回0
unsigned short trial(const size_t& i, const size_t& j, unsigned short k, const size_t& n, const size_t& m, const vector>& p, const vector>& t);   //在(i,j)单元上从k方向的下一个方向起寻找下一个可走方向,找到返回方向号，否则返回0

struct Record  //表示路径节点的结构体类型
{
    size_t x;
    size_t y;    //节点对应单元的行列标
    unsigned short mark;  //记录当前节点的后继节点对应的单元相对于当前节点对应的单元的方向
    Record(size_t x, size_t y, unsigned short m) :x(x), y(y), mark(m) {}
};

void outputPath(const vector &path_stack, const size_t &end_x, const size_t &end_y)
{
    for (const auto& run : path_stack)
        cout << "(" << run.x + 1 << "," << run.y + 1 << ")->";
    cout << "(" << end_x << "," << end_y << ")" << endl;
}

int main()
{
    size_t i, j; unsigned short k;   //i,j为单元位置标识,k为方向参数
    size_t m, n;   //m为迷宫行数,n为迷宫列数
    size_t Num;  //flag标志是否存在走出迷宫的路径,Num为找到的路径序号
    size_t min = 0, max = 0;
    string q;

    cout << "please input the number of row and col of the Maze matrix" << endl;
    cout << "please enter the row" << endl;
    cout << "row=";
    cin >> m;                     //输入迷宫矩阵行列数
    cout << "please enter the col" << endl;
    cout << "col=";
    cin >> n;

    vector> p(m, vector(n));  //p指向表示迷宫的二维数组,t指向记录迷宫中的每个位置是否已走过的二维数组
    vector> t(m, vector(n, false)); //初始化标志迷宫矩阵每一位置是否已走过的矩阵

    for (i = 0; i < m; i++)
    {
        cout << "please input the" << i + 1 << "nd row of Maze matrix" << endl;     //初始化迷宫矩阵,0表示可走,1表示障碍
        cin >> q;

        for (j = 0; j < n; j++)
            p[i][j] = static_cast (q[j] - 48);
    }

    vector path_stack;
    vector> min_path;
    vector> max_path;
    Num = 0;
    i = 0;
    j = 0;   //初始化当前单元行列标,将迷宫左上角单元作为出发点
    k = 0;   //方向参数初始化为0,对左上角单元从头开始试探可走方向

    while (true)
    {
        unsigned short temp;
        if ((temp = trial(i, j, k, n, m, p, t)) == 0)  //回溯试探开始
        {
            if (i == 0 && j == 0)  //在起始点已无方向可走,回溯结束
                break;

            if (k != 0)    //在(i,j)元上沿k方向后的所有方向均不可走,回溯
            {
                t[i][j] = false;
                path_stack.pop_back();    //(i,j)元节点弹出栈
            }
            //(i,j)元的所有方向均不可走,回溯
            const Record& back = path_stack.back();
            i = back.x;
            j = back.y;
            k = back.mark;
        }
        else
        {
            if (k == 0)   //从头开始为(i,j)元找到了可走方向trial(i, j, k, n, m, p, t)
            {
                path_stack.push_back(Record(i, j, temp));  //(i,j)元作为节点压入栈
                t[i][j] = true;    //(i,j)元标志为已走
            }
            else     //从k方向的下一方向开始为(i,j)元找到了可走方向trial(i, j, k, n, m, p, t)
                path_stack.back().mark = temp;    //相应更新(i,j)元节点中的方向

            convert(i, j, temp);   //沿找到的方向从(i,j)元递进至下一单元
            k = 0;   //为为下一单元从头开始寻找新方向作准备

            if (i == m - 1 && j == n - 1)    //抵达迷宫出口
            {
                Num++;             //找到路径数增1
                cout << endl << "The " << Num << "nd possible route:" << endl;   //输出路径序号
                outputPath(path_stack, m, n);

                if (min_path.empty())
                {
                    min_path.push_back(path_stack);
                    min = path_stack.size();
                }
                else
                {
                    if (path_stack.size() < min)
                    {
                        min_path.clear();
                        min_path.push_back(path_stack);
                        min = path_stack.size();
                    }
                    else if (path_stack.size() == min)
                        min_path.push_back(path_stack);
                }

                if (max_path.empty())
                {
                    max_path.push_back(path_stack);
                    max = path_stack.size();
                }
                else
                {
                    if (path_stack.size() > max)
                    {
                        max_path.clear();
                        max_path.push_back(path_stack);
                        max = path_stack.size();
                    }
                    else if (path_stack.size() == max)
                        max_path.push_back(path_stack);
                }

                const Record& back = path_stack.back();   //回溯
                i = back.x;
                j = back.y;
                k = back.mark;
            }
        }
    }

    if (min_path.empty())
        cout << "There is no possible route" << endl;
    else
    {
        cout << "There are " << Num << " routes in total" << endl;

        cout << "The length of shortest route is " << min + 1 << " shortest routes include:" << endl;
        for (const auto& run : min_path)
        {
            outputPath(run, m, n);
        }

        cout << "The length of longest route is " << max + 1 << " longest routes include:" << endl;
        for (const auto& run : max_path)
        {
            outputPath(run, m, n);
        }
    }
}

void convert(size_t &i, size_t &j, unsigned short k)
{
    switch (k)
    {
    case 1: --i; break;
    case 2: --i; ++j; break;
    case 3: ++j; break;
    case 4: ++i; ++j; break;
    case 5: ++i; break;
    case 6: ++i; --j; break;
    case 7: --j; break;
    case 8: --i; --j; break;
    }
}

bool boundary(const size_t& i, const size_t& j, unsigned short d, const size_t& n, const size_t& m)
{
    if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
    {
        if (i == 0 && j != 0)
        {
            if (j != n - 1)
            {
                if (m == 1)
                {
                    if (d == 8 || d == 1 || d == 2 || d == 6 || d == 5 || d == 4)
                        return false;
                    return true;
                }
                else
                {
                    if (d == 8 || d == 1 || d == 2)
                        return false;
                    return true;
                }
            }
            else
            {
                if (m == 1)
                {
                    if (d == 8 || d == 1 || d == 2 || d == 3 || d == 4 || d == 5 || d == 6)
                        return false;
                    return true;
                }
                else
                {
                    if (n == 1)
                    {
                        if (d == 8 || d == 1 || d == 2 || d == 3 || d == 4 || d == 6 || d == 7)
                            return false;
                        return true;
                    }
                    else
                    {
                        if (d == 8 || d == 1 || d == 2 || d == 3 || d == 4)
                            return false;
                        return true;
                    }
                }
            }
        }
        else
        {
            if (j == n - 1 && i != 0)
            {
                if (i != m - 1)
                {
                    if (n == 1)
                    {
                        if (d == 8 || d == 2 || d == 3 || d == 4 || d == 6 || d == 7)
                            return false;
                        return true;
                    }
                    else
                    {
                        if (d == 2 || d == 3 || d == 4)
                            return false;
                        return true;
                    }
                }
                else
                {
                    if (m == 1)
                    {
                        if (d == 8 || d == 1 || d == 2 || d == 3 || d == 4 || d == 5 || d == 6)
                            return false;
                        return true;
                    }
                    else
                    {
                        if (n == 1)
                        {
                            if (d == 8 || d == 2 || d == 3 || d == 4 || d == 5 || d == 6 || d == 7)
                                return false;
                            return true;
                        }
                        else
                        {
                            if (d == 2 || d == 3 || d == 4 || d == 5 || d == 6)
                                return false;
                            return true;
                        }
                    }
                }
            }
            else
            {
                if (i == m - 1 && j != n - 1)
                {
                    if (j != 0)
                    {
                        if (m == 1)
                        {
                            if (d == 8 || d == 1 || d == 2 || d == 4 || d == 5 || d == 6)
                                return false;
                            return true;
                        }
                        else
                        {
                            if (d == 4 || d == 5 || d == 6)
                                return false;
                            return true;
                        }
                    }
                    else
                    {
                        if (m == 1)
                        {
                            if (d == 8 || d == 1 || d == 2 || d == 4 || d == 5 || d == 6 || d == 7)
                                return false;
                            return true;
                        }
                        else
                        {
                            if (n == 1)
                            {
                                if (d == 8 || d == 2 || d == 3 || d == 4 || d == 5 || d == 6 || d == 7)
                                    return false;
                                return true;
                            }
                            else
                            {
                                if (d == 8 || d == 4 || d == 5 || d == 6 || d == 7)
                                    return false;
                                return true;
                            }
                        }
                    }
                }
                else
                {
                    if (i != 0)
                    {
                        if (n == 1)
                        {
                            if (d == 8 || d == 2 || d == 3 || d == 4 || d == 6 || d == 7)
                                return false;
                            return true;
                        }
                        else
                        {
                            if (d == 6 || d == 7 || d == 8)
                                return false;
                            return true;
                        }
                    }
                    else
                    {
                        if (m == 1)
                        {
                            if (d == 8 || d == 1 || d == 2 || d == 4 || d == 5 || d == 6 || d == 7)
                                return false;
                            return true;
                        }
                        else
                        {
                            if (n == 1)
                            {
                                if (d == 8 || d == 1 || d == 2 || d == 3 || d == 4 || d == 6 || d == 7)
                                    return false;
                                return true;
                            }
                            else
                            {
                                if (d == 8 || d == 1 || d == 2 || d == 6 || d == 7)
                                    return false;
                                return true;
                            }
                        }
                    }
                }
            }
        }
    }
    return true;
}

bool barrier(const size_t& m, const size_t& n, const vector>& p)
{
    if (p[m][n] == false)
        return true;
    return false;
}

bool visit(const size_t& m, const size_t& n, const vector>& t)
{
    if (t[m][n] == false)
        return true;
    return false;
}

bool direction(const size_t &i, const size_t &j, unsigned short d, const size_t& n, const size_t& m, const vector>& p, const vector>& t)
{
    if (boundary(i, j, d, n, m) == false) //(i,j)元在d方向为边界{
        return false;   //d方向不可走

    size_t m2 = i, n2 = j;
    convert(m2, n2, d);
    if (barrier(m2, n2, p) == false)  //(i,j)元在d方向遇到障碍
        return false;    //d方向不可走

    if (visit(m2, n2 ,t) == false)  //(i,j)元在d方向上的相邻单元已经走过
        return false;    //d方向不可走
    return true;    //d方向可走
}

unsigned short trial(const size_t &i, const size_t &j, unsigned short k, const size_t &n, const size_t &m, const vector> &p, const vector>& t)
{
    for (k++; k <= 8; k++)     //从k方向的下一方向开始寻找从(i,j)元可走的方向
    {
        if (direction(i, j, k, n, m, p, t) == 1)
            return k;      //找到可走方向，将其返回
    }

    return 0;   //没有可走方向，返回0
}