潜艇大冒险

家里的娃报名火花思维有一天收到了火花思维给寄来的一套很有趣的教具：潜艇大冒险。

这套玩具看上去很像小时候玩过的华容道。华容道是通过移动各种不同的棋子最终将曹操移动到下面中间处的出口，潜艇大冒险同样是移动各种棋子将潜水艇移动到下面中间处的出口。不同之处就在于潜艇大冒险的棋子更丰富一些，不但有些棋子有伸到外面的“耳朵”附件，而且通过旋转、排列不同的棋子可以摆出各种不同难度的棋局。教具中附带的文档给出了60个难度逐渐升高的棋局和对应答案，十分具有可玩性，孩子也十分喜欢。
在陪孩子玩的过程中，啊哈，灵机一动：这不就是一个很标准的DFS(深度优先搜索)问题吗？在每一步都会有2~3种走法，使用DFS进行暴力穷举就可以找出所有可能的解法。那就写个程序应用上DFS来解一下这个问题吧。

题目分析

首先是棋盘的设计。在这里可以用一个二维矩阵来代表棋盘，考虑到棋子和各种附加的“耳朵”附件，棋子的大小是不可能占用1✖️1大小的空间，所以这里将棋子的大小定义为5✖️5，横竖都是3排棋子也就是15✖️15。此外看图中潜水艇和大号的水雷都有可能伸出到棋盘的外面，所以在棋盘的四周还需要加上两排棋盘边，最后得出棋盘的大小应该为19乘以19，恰好和围棋的棋盘一样。棋盘的左上角作为坐标(0,0), 右下角为(18,18)。

下面就是棋子和附件的设计。前面已经提到过棋子的大小都是5✖️5，区别就是棋子的各种附件，按棋子的类别来分别设计一下：

1. 潜水艇✖️1。潜水艇有两个螺旋桨的附件，可以将其设计为两个2✖️2的矩阵；此外潜水艇的下面还有一个小夹子，这个小夹子也会阻碍棋子的移动，可以将其设计为一个1✖️1的矩阵。
2. 大水雷✖️1。大水雷就是上图中左下角的棋子，将大水雷定义为3✖️3的矩阵，其中1✖️1的角位于棋子之内，这样大水雷在左边和右边都伸出去了两排。
3. 中水雷✖️1。中水雷就是上图中大水雷之上的棋子，将中水雷定义为3✖️2的矩阵。上下各留出一个空行，然后一列位于棋子内部，伸出棋子的大小为一排。
4. 小水雷✖️5。小水雷定义为2✖️2的矩阵，位于棋子的一角上。小水雷按水雷位置的不同又分为3类：
   • 只有一个小水雷。
   • 有两个在同一边的小水雷。
   • 有两个在对角上的小水雷。

这样棋子都设计完了，需要注意的就是除了潜水艇，其它的棋子在初始拜访的时候都是可以旋转的。如上图中大水雷在棋子的左下角，那么左上、右上和右下都是可能的位置。

最后就是可移动性的判别。可以看到，棋子相互之间是不会阻碍移动的，起阻碍作用的都是棋子的附件，所以在移动的时候只需要判断是否有附件会造成阻碍即可。

程序设计

基于以上的分析，接下来就可以进行程序设计了。本文中的代码使用c++实现。

基类和enum

首先定义一下Point类，用来代表棋盘上的一个点, 重写了其+操作符方便后续进行位置计算。

class Point{

public:
    int x, y;
    Point(int i, int j) : x(i), y(j) {}
    ~Point() {}
    Point operator+(const Point &b)
    {
        return Point(x + b.x, y + b.y);
    }
};

接下来定义一下Square类，代表了棋盘上的一个方格的区域，作为棋子和附件类的基类使用。width 和 height 分别代表了这个方格的宽和高，leftTop代表了这个方格的左上角的坐标，这样就可以在棋盘上准确地定义方格所会覆盖的区域。此外定义了两个虚函数addToBoard和removeFromBoard用来在棋盘上添加和移除方格，添加失败则代表着出现了棋子或者附件冲突的非法操作，一般在棋盘初始化时棋子摆放错误造成的。

class Square
{
public:
    int width, height;
    Point leftTop;
    bool valid = false;

    Square(int w, int h) : leftTop(Point(-1, -1)), width(w), height(h){}

    virtual bool addToBoard(vector<vector<int>> &board, Point position)    {
    
        leftTop = position;
        return true;
    }
    virtual bool removeFromBoard(vector<vector<int>> &board) = 0;

    virtual ~Square() {}
};

在定义棋子和附件类之前，还需要定义几个enum数组，便于我们后续的编程操作。

//棋盘上的点当前的类型，NONE为棋盘上的空位置，CHESS和DECORATION分别代表了棋子和附件。
enum OBJECT_VALUE{

    NONE = 0,
    CHESS = 1,
    DECORATION = 2,
};

//附件在棋子上的位置，4个角加4条边，总共有8个位置。
enum POSITION{

    LEFT_TOP = 0,
    RIGHT_TOP = 1,
    LEFT_BOTTOM = 2,
    RIGHT_BOTTOM = 3,
    LEFT_BORDER = 4,
    TOP_BORDER = 5,
    RIGHT_BORDER = 6,
    BOTTOM_BORDER = 7,
};

//棋子移动的方向，由于棋子只能上下左右移动，所以有4个方向。
enum DERIECTION{

    LEFT = 0,
    UP = 1,
    DOWN = 2,
    RIGHT = 3,
};

//棋子的类型，分别是潜水艇、小水雷、中水雷和大水雷。
enum CHESS_TYPE{

    SUB_MARINE = 6,
    SMALL_MINE = 7,
    MIDDLE_MINE = 8,
    BIG_MINE = 9
};

附件类

定义好了上述的enum后就可以继续定义附件类。附件类继承自Square类，需要实现自己的addToBoard和removeFromBoard方法。其中addToBoard方法会在附件类的范围内判断附件是否超出了棋盘、是否被其它附件已经占用了等非法情况，如果出现非法情况则直接返回false代表添加附件失败。如果是合法的，则将棋盘上当前附件的区域的值都设置为2，代表当前附件添加到了棋盘上。removeFromBoard方法则很简单，遍历整个附件的区域，将所有区域的值改回为0，代表这部分棋盘为空，可以添加其它的棋子或者附件。

最重要的canMove方法，这个方法用来判断当前的附件可以向哪个方向移动。由于棋子的大小为5✖️5，而附件是跟随棋子移动的，所以其最大可以移动的距离就是5。在下面代码中，当需要判断是否可以向上移动的时候，只要判断附件最上面的一行从距离1到距离5是否可以移动即可。当移动过程中发现超出边界或者遇到其它的附件则代表不可移动，直接返回false。由于代码太长，这里略去了其它三个方向的判断代码，读者可以自行思考如何进行判断或者通过文章下面的链接下载源码查看实现方式。

class Decoration : public Square
{
public:
    Decoration(int width, int height) : Square(width, height){}

    virtual ~Decoration() {}

    bool canMove(vector<vector<int>> &board, DERIECTION deriction)    {
    
        for (int move = 1; move <= 5; move++)
        {
            switch (deriction)
            {
            case UP:
                for (int i = leftTop.x, j = leftTop.y; j < leftTop.y + width; j++)
                {
                    if (i - move < 0 || board[i - move][j] == DECORATION)
                    {
                        return false;
                    }
                }
                break;
            case DOWN: ...
                break;
            case LEFT: ...
                break; 
            case RIGHT: ...
                break;
            }
        }
        return true;
    }

    virtual bool removeFromBoard(vector<vector<int>> &board) override    {
    
        for (int i = 0; i < height; i++)
        {
            for (int j = 0; j < width; j++)
            {
                int x = leftTop.x + i;
                int y = leftTop.y + j;
                if (board[x][y] == DECORATION)
                {
                    board[x][y] = NONE;
                }
            }
        }
        return true;
    }

    virtual bool addToBoard(vector<vector<int>> &board, Point position) override    {
    
        Square::addToBoard(board, position);
        
        if (position.x < 0 || position.x > 19 || position.y < 0 || position.y > 19)
        {
            return false;
        }
        for (int i = 0; i < height; i++)
        {
            for (int j = 0; j < width; j++)
            {
                int x = leftTop.x + i;
                int y = leftTop.y + j;
                if (board[x][y] == DECORATION)
                {
                    //Confilct with other decoration
                    cout << "board x:" << x << " y:" << y << " is ocupied by DECORATION" << endl;
                    valid = false;
                    return false;
                }
                else
                {
                    board[x][y] = DECORATION;
                }
            }
        }
        return true;
    }
};

定义好了附件类，就可以很轻松地将所有的附件给定义出来了，只需要指定对应附件的大小即可。

//小水雷，大小为2✖️2。
class SmallMine : public Decoration
{
public:
    SmallMine() : Decoration(2, 2)
    {
    }
    ~SmallMine() {}
};

//中水雷，大小为2✖️3，水平放置时为3✖️2。
class MiddleMine : public Decoration
{
public:
    MiddleMine() : Decoration(2, 3)
    {
    }
    MiddleMine(bool horizental) : Decoration(3, 2)
    {
    }
    ~MiddleMine() {}
};

//大水雷，大小为3✖️3。
class BigMine : public Decoration
{
public:
    BigMine() : Decoration(3, 3)
    {
    }
    ~BigMine() {}
};

//螺旋桨，大小为2✖️2。
class Propeller : public Decoration
{
public:
    Propeller() : Decoration(2, 2)
    {
    }
    ~Propeller() {}
};

//小夹子，大小为1✖️1。
class Clip : public Decoration
{
public:
    Clip() : Decoration(1, 1)
    {
    }
    ~Clip() {}
};

棋子类

棋子基类Chess同附件类一样也继续了Square类并实现了自己的addToBoard和removeFromBoard方法, 其实现与附件类基本相同，但是会添加对附件的操作，下面代码中省略掉了具体实现。棋子类内部有个数组decorations用来保存当前棋子所有的附件，不同棋子有不同种类和数量的附件。由于所有的棋子大小都是5✖️5，所有在构造方法中直接调用Square的构造方法并将方格的大小设置为5✖️5。虚函数chessType 由子类来实现返回子类的棋子类型。

在棋子类的canMove方法中，需要根据棋子的类型和附件的排列方式来判断是否可以移动。如有两个小水雷的棋子，并且这两个小水雷在同一列上，当需要判断是否能向上移动的时候，我们只需要判断上面的那个小水雷是否可以移动即可，否则会出现下面的小水雷被上面的所阻碍的情况，从而造成判断错误。而对于潜水艇来讲，当处于出口位置时，我们就需要忽略小夹子向下是否可以移动，因为小夹子必然会超出棋盘的范围。

需要注意的是析构函数中需要delete棋子中的所有附件类指针，当然我们也可以使用智能指针来简化这部分逻辑。

class Chess : public Square
{
public:
    vector<pair<Decoration *, Point>> decorations;
    Chess() : Square(5, 5) {}

    virtual CHESS_TYPE chessType() = 0;
    ...

    bool canMove(vector<vector<int>> &board, DERIECTION deriction)    {
    
        if (decorations.size() == 3)
        { // Check the clip of submarine chess.
            auto clip = decorations[1].first;
            if (deriction == DOWN && clip->leftTop.x == 16 && clip->leftTop.y == 9)
            {
                //Skip the check for clip in the exit position for down deriction.
            }
            else
            {
                if (!clip->canMove(board, deriction))
                    return false;
            }
        }

        auto front = decorations.front().first;
        auto back = decorations.back().first;

        if (decorations.size() == 1)
        {
            return front->canMove(board, deriction);
        }
        else
        {
            auto frontLeftTop = front->leftTop;
            auto backLeftTop = back->leftTop;
            //Check for the situations that two decorations are in the same line and deriction.
            switch (deriction)
            {
            case UP:
                if (sameCol(frontLeftTop, backLeftTop))
                {
                    //For up, we only need to check the upper one.
                    return (frontLeftTop.x < backLeftTop.x ? front : back)
                        ->canMove(board, deriction);
                }
                break;
            case DOWN: ...
                break;
            case LEFT: ...
                break;
            case RIGHT: ...
                break;
            default:
                break;
            }
        }
        return (front->canMove(board, deriction) && back->canMove(board, deriction));
    }
    
    virtual bool removeFromBoard(vector<vector<int>> &board) override    {
    
        ...
    }
    
    virtual bool addToBoard(vector<vector<int>> &board, Point position) override    {
    
        ...
    }
    
    virtual ~Chess()
    {
        for (auto decoration : decorations)
        {
            delete decoration.first;
        }
    }
};

有了棋子基类就可以继续定义各种不同的棋子类。不同的棋子类要添加上不同的附件，并需要根据附件的位置来计算好附件的正确坐标。特别是各种水雷类，由于水雷有各种不同的摆放位置，所以需要针对每个位置进行判断。

class SubMarine : public Chess
{
public:
    SubMarine() : Chess()
    {
        //Add two propellers on top left and top right.
        decorations.push_back({new Propeller(), {0, -2}});
        decorations.push_back({new Clip(), {4, 2}});
        decorations.push_back({new Propeller(), {0, width}});
    }
    ~SubMarine() {}
    CHESS_TYPE chessType() override    {
    
        return SUB_MARINE;
    }
};

class SmallMineChess : public Chess
{
public:
    SmallMineChess(vector<POSITION> positions) : Chess()
    {
        for (auto position : positions)
        {
            if (position > RIGHT_BOTTOM)
            {
                cout << "SmallMine must on four corners!" << endl;
                valid = false;
                return;
            }

            switch (position)
            {
            case LEFT_TOP:
                decorations.push_back({new SmallMine(), {0, 0}});
                break;
            case RIGHT_TOP:
                decorations.push_back({new SmallMine(), {0, width - 2}});
                break;
            case LEFT_BOTTOM:
                decorations.push_back({new SmallMine(), {height - 2, 0}});
                break;
            case RIGHT_BOTTOM:
                decorations.push_back({new SmallMine(), {height - 2, width - 2}});
                break;
            default:
                cout << "wrong position" << position << endl;
            }
        }
    }

    ~SmallMineChess() {}
    CHESS_TYPE chessType() override    {
    
        return SMALL_MINE;
    }
};

class MiddleMineChess : public Chess
{
public:
    MiddleMineChess(POSITION position) : Chess()
    {

        if (position < RIGHT_BOTTOM)
        {
            cout << "MiddleMine must on four borders!" << endl;
            valid = false;
            return;
        }

        switch (position)
        {
        ...
        }
    }
    ~MiddleMineChess() {}
    CHESS_TYPE chessType() override    {
    
        return MIDDLE_MINE;
    }
};

class BigMineChess : public Chess
{
public:
    BigMineChess(POSITION position) : Chess()
    {
        if (position > RIGHT_BOTTOM)
        {
            cout << "BigMine must on four corners!" << endl;
            valid = false;
            return;
        }

        switch (position)
        {
        ...
        }
    }
    ~BigMineChess() {}
    CHESS_TYPE chessType() override    {
    
        return BIG_MINE;
    }
};

算法实现

至此所有的准备工作都已经完成了，下面就可以具体地来实现DFS算法, 为了便于调试定义了一个printBoard方法将棋盘整个打印出来，如下图所示打印出来的就是第一关的示意图。中间是8个棋子和一个空格，周围是多出来的两排“棋盘边”，可以让伸出来的附件在上面移动。

接下来就是算法的实现。findPath方法是程序的接口，接收从外部传入的棋盘和棋子数据，其中的棋子数据就是一个3✖️3的二维数组，里面保存的就是棋子在真实棋盘中的初始位置。找出其中的空格作为算法的起始位置之后调用dfsFind方法开始启动深度优先算法。算法的流程如下：

1. 以当前的空格为起点，依次遍历4个方向，排除掉来的方向之后从剩下的方向中找到一个可以移动的方向。
2. 如果发现一个可移动的方向就将当前的移动方向加入到path中，这是我们最后获取到答案的依据。
3. 将这个可移动的棋子从棋盘中删除。
4. 在棋子数组中移动这个棋子到新的位置。
5. 将移动到新位置的棋子重新添加到棋盘上。此时我们需要看下潜水艇棋子是否移动到了下面中间的出口位置。当潜水艇棋子移动到这个位置的时候如果它还可以往下移动那就是找到了一条解题的路径。
6. 如果上一步没有找到解那说明还需要继续寻找，递归地调用dfsFind方法进行寻找。
7. 当前方向上没有找到解，说明当前方向上是无解的，需要恢复棋盘和棋子的状态到步骤2之前，继续查找下一个方向。

以上就是算法的整体实现，如果对深度优先算法不太了解可能理解起来会有点困难，可以先看一下前面对深度优先算法总结的文章，理解深度优先算法后再来看这里的算法就会很清晰了。此外要想程序运行起来还需要实现题目的输入和输出，在本文中将不再赘述，感兴趣的读者可以自行查看源码。

class SubmarineWar
{
private:
    pair<int, int> moveDeriction[4] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
    int maxStep;
    int showLog;
    int findShortest;

public:
    SubmarineWar(int _maxStep, int _showLog, int _findShortest) : maxStep(_maxStep), showLog(_showLog), findShortest(_findShortest) {}
    ~SubmarineWar() = default;
    void printBoard(vector<vector<int>> &board)    {
    
        ...
    }

    vector<int> findPath(vector<vector<Chess *>> &chesses, vector<vector<int>> &board)
    {
	    if(chesses.size() != 3 || chesses[0].size() != 3 || board.size() != 19 || board[0].size() != 19) {
            cout<<"chesses or board size error!"<<endl;
            return {};
        }
        
        if (showLog)
        {
            printBoard(board);
        }
        
        vector<int> path;
        vector<int> minPath;
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {

                if (!chesses[i][j])
                {
                    dfsFind(chesses, board, path, minPath, i, j);
                    if (!minPath.empty())
                    {
                        // cout << "Find a path" << endl;
                        return minPath;
                    }
                }
            }
        }
        return {};
    }

private:
    //(x,y) is the empty chess location.
    bool dfsFind(vector<vector<Chess *>> &chesses, vector<vector<int>> &board, vector<int> &path, vector<int> &minPath, int x, int y)    {
    

        if (path.size() > maxStep)
        {
            return false;
        }

        for (int i = 0; i < 4; i++)
        {
            if ((!path.empty() && path.back() == i))
            {
                //The deriection last step comes from.
                continue;
            }
            int nextX = x + moveDeriction[i].first;
            int nextY = y + moveDeriction[i].second;
            if (nextX < 0 || nextX > 2 || nextY < 0 || nextY > 2)
            {
                continue;
            }

            //1. Find a valid movable deriction.
            if (chesses[nextX][nextY]->canMove(board, DERIECTION(3 - i))) //Move to the current empty position.
            {
                //2. Save the path.
                path.push_back(3 - i);

                //3. Remove this chess from board.
                chesses[nextX][nextY]->removeFromBoard(board);
                //4. Move this chess in chess array.
                chesses[x][y] = chesses[nextX][nextY];
                chesses[nextX][nextY] = nullptr;

                //5. Add this chess to the board with the target position.
                if (!chesses[x][y]->addToBoard(board, {2 + x * 5, 2 + y * 5}))
                {
                    cout << "add to board failed" << endl;
                    return false;
                }

                if (x == 2 && y == 1 && chesses[x][y]->chessType() == SUB_MARINE)
                {
                    if (chesses[x][y]->canMove(board, DOWN))
                    {
                        path.push_back(DOWN);
                        if (maxStep > path.size())
                        {
                            minPath = path;
                            maxStep = minPath.size();
                            if (!findShortest)
                            {
                                return true;
                            }
                        }
                        path.pop_back();
                    }
                }

                //6. Do dfs search.(nextX, nextY) shoule be empty chess.
                if (dfsFind(chesses, board, path, minPath, nextX, nextY))
                {
                    //find a path
                    if (!findShortest)
                    {
                        return true;
                    }
                }

                //7. Revert chess position
                chesses[x][y]->removeFromBoard(board);
                chesses[nextX][nextY] = chesses[x][y];
                chesses[x][y] = nullptr;
                if (!chesses[nextX][nextY]->addToBoard(board, {2 + nextX * 5, 2 + nextY * 5}))
                {
                    cout << "add to board failed" << endl;
                    return false;
                }

                path.pop_back();
            }
        }
        return false;
    }
};

总结

其实深度优先算法不是本文中的难点，真正的难点是对棋子和附件类的设计以及对是否可移动的判断。在实现过程中，由于附件种类很多并且还涉及到各个移动方法，所以是否可移动是出现bug最多的地方。实现过程中由于设计的失误也出现不少返工，将各个细节都想清楚后再实现应该可以节省不少时间的，真是应了那句老话“磨刀不误砍柴工”。

最后附上文中的程序源码链接：https://github.com/Chaoba/SubmarineWar, 感兴趣的读者可以自行阅读并运行源码并欢迎提出宝贵意见。