数据结构之——栈在扫雷问题中的应用

栈的定义是限定仅在表尾进行插入或删除操作的线性表。它的主要特点就是后进先出，通过压栈和出栈对表尾元素进行插入和删除。

迷宫问题作为使用栈解决的经典问题，给我很大的启示，迷宫问题之所以能采用穷举法获取一条正确路径的原因就是因为使用了栈这一数据结构，从栈的主要特点分析来看，它能给我们提供一种解决某种问题的思路，那就是需要记录已经处理过的信息的时候，用栈是个不错的选择。在迷宫问题中就是记录已走过的路径。而记录这路径有何用？因为当遇到走不通的时候，需要按原路返回，而不是在原地打转，所以这时候栈中信息就至关重要，我们让这些信息出栈，就能实现“退一步”的操作了。重复如此，采用“穷举法”就可获得正确的路径。

同理，扫雷中同样存在栈的应用，在什么地方呢？就是在当你点击的方格是空白的时候，周围与之相连的空白立刻会显示。要实现这一功能需要用到栈，但是却又与迷宫问题有所区别，就是迷宫问题需要的是一条路径，而扫雷需要的多条，但不管是一条还是多条，我们都可以用栈实现。

如下图：

图 1

图 2

上图为扫雷中 9x9 格的布局，当点击的是空白时，周围的与之相连空白也连带显示。

具体的思路就是：

图 3

代码如下：

//本代码使用的是字符串模拟栈，通过对字符串的尾部进行插入和删除实现入栈和出栈
void ShowSafetyZone(int x, int y)
{
    int i = 1;//标识方向默认向右
    CurrentPositon = ConverToString(x, y);
    do
    {
        //如果当前位置可达
        if (PassEnable(CurrentPosition) == ture)
        {
            //留下足迹
            FootPrint(CurrentPosition);
 
            //将当前位置压入栈中
            AddToStack(CurrentPosition);
 
            //显示当前位置周围的数字
            ShowArroundNum(CurrentPosition);
 
            //计算下一步的位置
            CurrentPosition = NextPosition(CurrentPosition, i);
        }
 
        //如果当前位置不可达
        else
        {
            //后退一步
            CurrentPosition = Strings.Right(stack, 4);
 
            //判断当前位置右边是否可达
            if (PassEnable(NextPosition(CurrentPosition, 1)) == True)
            {
                i = 1;
                //如果可达就移动到右边
                CurrentPosition = NextPosition(CurrentPosition, 1);
                continue;
            }
            else if (PassEnable(NextPosition(CurrentPosition, 2)) == True)
            {
                i = 2;
                //如果可达就移动到下边
                CurrentPosition = NextPosition(CurrentPosition, 2);
                continue;
            }
            else if (PassEnable(NextPosition(CurrentPosition, 3)) == True)
            {
                i = 3;
                //如果可达就移动到左边
                CurrentPosition = NextPosition(CurrentPosition, 3);
                continue;
            }
            else if (PassEnable(NextPosition(CurrentPosition, 4)) == True)
            {
                i = 4;
                //如果可达就移动到上边
                CurrentPosition = NextPosition(CurrentPosition, 4);
                continue;
            }
            else
            {
                if (Strings.Len(stack) >= 4)
                {
                    //出栈
                    DropFromStack();
                    //初始化方向
                    i = 1;
                }
                //后退一步
                if (Strings.Len(stack) >= 4)
                    CurrentPosition = Strings.Right(stack, 4);
            }
        }
    }
    //当栈不为空时，继续循环
    while (Strings.Len(stack) >= 4)
}