【数据结构】使用栈Stack解决迷宫问题

      我们看下面这个迷宫----方阵（也可以是矩阵）：

创新互联建站致力于互联网品牌建设与网络营销，包括成都网站设计、网站建设、SEO优化、网络推广、整站优化营销策划推广、电子商务、移动互联网营销等。创新互联建站为不同类型的客户提供良好的互联网应用定制及解决方案，创新互联建站核心团队10多年专注互联网开发，积累了丰富的网站经验，为广大企业客户提供一站式企业网站建设服务，在网站建设行业内树立了良好口碑。

     迷宫入口是坐标（2，0）位置，出口是（9，3）。我们假定0代表通路，1代表不通。

     现在需要找到哪一条路是通路。我们的思想是借助栈，“回溯法”。回溯是什么意思呢？？？先从起点出发，检查它的上下左右是否是通路（即是否有为数字0处）。也就是说为0通了，压栈，将此位置元素变成2，这样做的好处是明确通路路径。然后继续往下走，判断上下左右 。直至我们找到终点（纵坐标在矩阵的最后一行）。

     我们来看下我针对迷宫问题实现的代码：

#include
#include
#define N 10    //该迷宫10*10.

struct Pos    //定义一个结构体，该结构体用来表示坐标。
{
    int _row;
    int _col;

    Pos(int row,int col)
        :_row(row)
        , _col(col)
    {}
};


template
bool SearchMazePath(int* a, int n, Pos entry, stack& paths)    //寻找迷宫是否有通路。
{
    assert(a);
    
    paths.push(entry);
    while (!paths.empty())
    {
        Pos cur = paths.top();
        a[cur._row*n + cur._col] = 2;            
        if (cur._row == n - 1)
        {
            return true;
        }

        //上
         Pos tmp = cur;
        --tmp._row;
        if (a[tmp._row*n + tmp._col] == 0)
        {
            paths.push(tmp);
            continue;
        }
        
        //下
        tmp = cur;    
        ++tmp._row;
        if (a[tmp._row*n + tmp._col] == 0)
        {
            paths.push(tmp);
            continue;
        }
        
        //左
        tmp = cur;        
        --tmp._col;
        if (a[tmp._row*n + tmp._col] == 0)
        {
            paths.push(tmp);
            continue;
        }
        
         //右
       tmp = cur;
        ++tmp._col;
        if (a[tmp._row*n + tmp._col] == 0)
        {
            paths.push(tmp);
            continue;
        }
        
        paths.pop();    //若上下左右都不通，则回溯。
    }
    
    return false;
}


void GetMaze(int* a, int n)    //读取到迷宫图案
{
    assert(a);
    FILE* fout = fopen("MazeMap.txt", "r");
    assert(fout);    //若文件打开失败，后续工作则无法完成，因此采用assert防御式编程。
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            while (true)
            {
                int men = fgetc(fout);    //读取字符
                if (men == '0' || men == '1')    //是0或者1则转换成数字到二维矩阵中存储。
                {
                    a[i*n + j] = men -'0';
                    break;    
                }                
            }
        }
    }       
}

void PrintMaze(int* a, int n)    //将此迷宫打印出来
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n;j++ )
        {
            cout << a[i*n + j] << "  ";
        }
        cout << endl;
    }
    cout << endl;
}


void Test()
{
    int a[N][N] = {};
    Pos sp(2, 0);    //入口坐标
    
    GetMaze((int*) a, N);
    PrintMaze((int*)a, N);
    stack paths;
    
    SearchMazePath((int*)a, N, sp, paths);  
    //二维数组实际存储是一维数组，将二维数组强制转换为一维数组传参。
    PrintMaze((int*)a, N);
}


int main()
{
    Test();
    system("pause");
    return 0;
}

      有时候，针对迷宫问题，我们还需要求多条路径的最优解（最短路径）。那这时候我们可以用压栈，利用栈帧一层一层压栈的特点实现。