在计算机中，我们可以把迷宫当做一个二维数组。其中0表示通路，1表示墙。
我们以下图为例，对于只有一条通路的简单迷宫进行求解
该迷宫存储在“Map.txt”文档中。
对于该迷宫，我们首先将入口点压入栈中，然后通过对该点的上、右、下、左分别进行探测，找到合适的点前进，并将该点压入栈中。为了防止将已经走过的点再走一遍，我们需要对已走过的点进行赋值，将其赋为2.当点继续前进的时候很容易会进入到一个死胡同当中，即从这个点到其他点没有通路，我们需要运用到回溯法。回溯法就是将已将压栈的点进行出栈，为了区分那些点是不是经过了出栈，我们将那些出栈的点赋为3。运用回溯法我们可以测试之前的点还有没有其他的通路，依次查找。最终，我们就会找到迷宫的出口。
对于该迷宫的求解代码如下：
#include<iostream>
#include<assert.h>
#include<stack>#pragma warning(disable:4996)using namespace std;const size_t N = 10;void InitMap(int maze[][N], size_t n)
{FILE* map = fopen("Map.txt", "r");assert(map);for (size_t i = 0; i < n; ++i){for (size_t j = 0; j < n;){char ch = fgetc(map);if (ch == '0' || ch == '1'){maze[i][j] = ch - '0';++j;}}}
}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;}cout << endl;
}struct Pos
{size_t _row;size_t _col;
};bool CheckWay(int maze[][N], size_t n, Pos& pos)
{if (maze[pos._row][pos._col] == 0){return true;}else{return false;}
}bool GetPath(int maze[][N], size_t n, Pos& entry)
{stack<Pos> path;path.push(entry);while (!path.empty()){Pos cur = path.top();Pos next;maze[cur._row][cur._col] = 2; //走过的节点标记为2if (cur._row == n - 1) //最后一行为出口{return true;}//上next = cur;--next._row;if (CheckWay(maze, n, next)){path.push(next);continue;}//右next = cur;++next._col;if (CheckWay(maze, n, next)){path.push(next);continue;}//下next = cur;++next._row;if (CheckWay(maze, n, next)){path.push(next);continue;}//左next = cur;--next._col;if (CheckWay(maze, n, next)){path.push(next);continue;}//该点附近没有通路,使用回溯法Pos prev = path.top();maze[prev._row][prev._col] = 3; //退回的标记为3path.pop();}return false;
}void TestMaze()
{int maze[N][N];InitMap(maze, N);PrintMap(maze, N);Pos entry;entry._row = 2;entry._col = 0;GetPath(maze, N, entry);PrintMap(maze, N);
}int main()
{TestMaze();return 0;
}这段代码的运行结果为：
我们可以很清晰的看到迷宫的解，并且我们能发现这个迷宫是如何求解的。
