求迷宫通路问题

迷宫通路问题"/>

求迷宫通路问题

    本次我们探讨一下迷宫小游戏。

让我们来探讨一下怎样可以得到一条通路，采用栈来实现。

    当是通路的时候，节点压栈。当走到尽头不通时，出栈，寻找交叉口，寻找通路。

像这样在第一行存放迷宫的规格（在这里为传参少，定义正方形迷宫），设计迷宫，将迷宫以.txt格式存放在目录下（可以是任何地方，下文以默认路径为例）。

    假设入口为(2,0)，出口为迷宫最后一行任意位置。

    MAZE.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<assert.h>
#include<stack>class Pos  //迷宫每一点的坐标
{
public:Pos(int row,int col):_row(row), _col(col){}int _row;int _col;
};void PrintPos(Pos& pos)// 打印节点坐标
{cout << "(" << pos._row << ", " << pos._col << ") ";
}int* GetMaze(int& N)//从文件中打开迷宫
{FILE *font = fopen("maze.txt", "r");assert(font != NULL);//打不开迷宫文件无意义char ch;while ((ch = fgetc(font)) != '\n'){N = N * 10 + ch - '0';}int *a = new int[N*N];for (int i = 0; i < N*N, (ch = fgetc(font)) != EOF;){if (ch == '1' || ch == '0'){a[i] = ch - '0';i++;}}return a;
}void PrintMaze(int *a, const int N)//打印迷宫
{cout << "\n迷宫地图  ('0'为路, '1'为墙)" << endl;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){cout << a[i * 10 + j] << " ";}cout << endl;}
}bool IsOverScope(Pos pos, const int N)//判断是否越界
{if (pos._col < 0 || pos._col >= N || pos._row < 0 || pos._row >= N){return true;}return false;
}bool IsEndPoint(Pos pos, const int N)  //判断是否为终点：设迷宫终点为能到达迷宫N-1行
{if (pos._col >= 0 && pos._col < N && pos._row == N - 1){return true;}return false;
}bool SearchMazePath(int* a, const int N, Pos enrty, stack<Pos>& paths) //寻找通路
{//若某一位置节点为0，进行压栈，且将数据改为2，寻找此节点上下左右位置为0的节点，再进行压栈，//若某一位置上下左右没有为0的节点，就出栈寻找上一个节点上下左右为0的节点进行压栈 assert(a);Pos top = paths.top();a[top._row*N + top._col] = 2;while (!IsOverScope(paths.top(), N))//每次都要判断坐标是否越界、还要考虑出口旁边也是出口的情况就会多走几次{//判断是否到达出口if (IsEndPoint(top, N)){return true;}if (0 == a[(top._row - 1)*N + top._col])//上{a[(top._row - 1)*N + top._col] = 2;Pos tmp(top._row - 1, top._col);paths.push(tmp);top = paths.top();continue;}if (0 == a[top._row * N + top._col + 1])//右{a[top._row * N + top._col + 1] = 2;Pos tmp(top._row, top._col + 1);paths.push(tmp);top = paths.top();continue;}if (0 == a[(top._row + 1)*N + top._col])//下{a[(top._row + 1)*N + top._col] = 2;Pos tmp(top._row + 1, top._col);paths.push(tmp);top = paths.top();continue;}if (0 == a[top._row * N + top._col - 1])//左{a[top._row * N + top._col - 1] = 2;Pos tmp(top._row, top._col - 1);paths.push(tmp);top = paths.top();continue;}//if (0 == a[top._row * N + top._col + 1] && top._col + 1 < N)//右//{// a[top._row * N + top._col + 1] = 2;// Pos tmp(top._row, top._col + 1);// paths.push(tmp);// top = paths.top();// continue;//}//回退if (a[top._row*N + top._col] == 2 && !paths.empty()){paths.pop();if (!paths.empty()){top = paths.top();   continue;}else{return false;}}}//if (IsOverScope(top, N) || paths.empty())//从上左右出来 return false;}void PrintPath(stack<Pos> paths)  //打印通路
{//最少Paths中有一个元素enrty在最底层assert(!paths.empty());cout << "通路： " << endl;;while (!paths.empty()){PrintPos(paths.top());paths.pop();}cout << endl;
}

    test.cpp

#include"MAZE.h"void test()
{//假设迷宫为N*N型正方形int N = 0;int *a = GetMaze(N);PrintMaze(a, N);Pos enrty(2,0);stack<Pos> paths;paths.push(enrty);if (SearchMazePath((int*)a, N, enrty, paths)){PrintMaze(a, N);PrintPath(paths);}else{PrintMaze(a, N);cout << "There is not a path in this maze!" << endl;}}int main()
{test();system("pause");return 0;
}

让我们来看看运行结果。

再试试将最后一行的‘0’改为1，让它变成无通路的迷宫

我们可以在思考一下：

    当有好几条通路的时候，我们可以得到最短路吗？

我们可以得到以下思路：

    记录最小路的步数 ,到达出口时将出口变为1 ,寻找下一条出口,然后更新最短路.

若要寻找这条最短路，那就可以在寻找一次，当通路的步数与最短路步数一致时输出通路。

    但是上述方法存在很大的问题：虽然可以得到一个结果，但是不能够保证就是最短的。

因为，当按照上述编程寻找通路的逻辑 “上右下左” 顺序寻找通路时，就可能会把另一条更短的通路堵住，从而影响最短路的结果。

那到底怎么做呢？ 期待下一篇博客。