迷宫问题：
在一个拥有墙壁和空地的迷宫中，输入终点和起点，有程序搜索可通路径。
解法思路：
从起点出发，先记录当前节点能探索的方向。然后依次向一个方向探索，直到这个方向不能继续探索再切换方向。如果当前位置所
有方向的探索均结束，却没有到达终点，则沿
路返回当前位置的前一个位置，并在此位置还
没有探索过的方向继续进行探索；直到所有可
能的路径都被探索到为止。为了保证在任何位置上都能原路返回，因此需要使用一个后进先出的存储结构来保存从
起点到当前位置的路径以及在路径上各位置还可能进行探索的方向。因此在迷宫问题中使用
堆栈是自然的。
迷宫
迷宫的二维数组模拟
其中1表示墙壁，0表示空地，*表示路径。
定义迷宫路格
private class Cell
{
int x = 0; //单元所在行
int y = 0; //单元所在列
bool visited = false; //是否访问过
char c = ' '; //是墙('1')、可通路('0')或起点到终点的路径('*')
public Cell(int x, int y, char c, bool visited)
{
this.x = x; this.y = y;
this.c = c; this.visited = visited;
}
}
伪代码描述：
while(堆栈不空){
取出栈顶位置作为当前位置；
如果 当前位置是终点，
则 使用堆栈记录的路径标记从起点至终点的路径；
否则{ 按照向下、右、上、左的顺序将当前位置下一个可以探索的位置入栈；
//从堆栈取出的探索方向顺序则是左、上、右、下
如果 当前位置没四周均不可通
则 当前位置出栈；
}
}
代码描述：
while (!stack.isEmpty())
{
Cell current = (Cell)stack.peek();
if (current == endCell)
{ //路径找到
while (!stack.isEmpty())
{
Cell cell = (Cell)stack.pop();//沿路返回将路径上的单元设为*
cell.c = '*';
//堆栈中与 cell 相邻的单元才是路径的组成部分，除此之外，
//堆栈中还有记录下来但是未继续向下探索的单元，
//这些单元直接出栈
while (!stack.isEmpty() && !isAdjoinCell((Cell)stack.peek(), cell)) stack.pop();
}
Console.WriteLine("找到从起点到终点的路径。");
printMaze(cells);
return;
}
else
{ //如果当前位置不是终点
int x = current.x;
int y = current.y;
int count = 0;
if (isValidWayCell(cells[x + 1][y]))
{ //向下
stack.push(cells[x + 1][y]); cells[x + 1][y].visited = true; count++;
}
if (isValidWayCell(cells[x][y + 1]))
{ //向右
stack.push(cells[x][y + 1]); cells[x][y + 1].visited = true; count++;
}
if (isValidWayCell(cells[x - 1][y]))
{ //向上
stack.push(cells[x - 1][y]); cells[x - 1][y].visited = true; count++;
}
if (isValidWayCell(cells[x][y - 1]))
{ //向左
stack.push(cells[x][y - 1]); cells[x][y - 1].visited = true; count++;
}
if (count == 0) stack.pop();//如果是死点，出栈
}//end of if
}//end of while
1.判断是否为当前点的相邻点
private bool isAdjoinCell(Cell cell1, Cell cell2)
{
if (cell1.x == cell2.x && Math.abs(cell1.y - cell2.y) < 2) return true;
if (cell1.y == cell2.y && Math.abs(cell1.x - cell2.x) < 2) return true;
return false;
}
2.判断当前路格是否为空地且没走过
private boolean isValidWayCell(Cell cell){
return cell.c=='0'&&!cell.visited;
}
