博客

迷宫问题可以抽象为一个二维数组来求解，假设有如图示的迷宫：



解题思路：

用一个栈来存放当前人的位置的坐标，并每次测试当前位置的上、下、左、右，看哪个位置可以继续前进，可以继续前进的位置入栈，并且将人走过的位置的值赋值为2，以此来区分在测试的是时候不会往回走，直至走进死胡同的时候，将走过的位置出栈，并再测试可以前进的位置，依次循环，直至找到出口。

本例代码：

#pragma once

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

const int N = 10;

int MazeMap[N][N] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
};

void PrintMap(int maze[][N], size_t N) 
{
    for (size_t i = 0;i < N;++i)
    {
        for (size_t j = 0;j < N;++j)
        {
            cout << maze[i][j]<<" ";
        }
        cout << endl;
    }
}

struct Pos
{
    size_t i;
    size_t j;
};

bool IsGoingOn(int maze[][N], size_t N,Pos& pos)
{
    if (maze[pos.i][pos.j ] != 0)
        return false;
    else 
    {
        return true;
    }
}
void GetTheWay(int maze[][N], size_t N)
{
    PrintMap(MazeMap,N);
    Pos entry = { 2,0 };
    stack<Pos> sp;
    sp.push(entry);
    while (!sp.empty())
    {
        Pos cur = sp.top();
        Pos next;
        maze[cur.i][cur.j] = 2;//将走过的位置赋值为2，用以区分
        if (cur.i == 9)//本例特殊的出口
        {
            maze[cur.i][cur.j] = 2;
            cout << endl<<"finish!" << endl;
            break;
        }   
            //右
            next = cur;
            next.i = cur.i;
            next.j = cur.j + 1;
            if (IsGoingOn(MazeMap, N, next))
            {
                sp.push(next);
                continue;
            }
            //下
            next = cur;
            next.j = cur.j;
            next.i = cur.i + 1;
            if (IsGoingOn(MazeMap, N, next))
            {
                sp.push(next);
                continue;
            }

            //上
            next = cur;
            next.i = cur.i - 1;
            next.j = cur.j;
            if (IsGoingOn(MazeMap, N, next))
            {
                sp.push(next);
                continue;
            }

            //左
            next = cur;
            next.i = cur.i;
            next.j = cur.j - 1;
            if (IsGoingOn(MazeMap, N, next))
            {
                sp.push(next);
                continue;
            }

            //出栈之前将该位置的值赋值为3
            //以此来表示回溯路径
            Pos back = sp.top();
            maze[back.i][back.j] = 3;
            sp.pop();
    }

}

void Test()
{
    GetTheWay(MazeMap, N);
    PrintMap(MazeMap, N);
}

运行结果：