POJ 3009 Curling 2.0 {深度优先搜索}

原题

$On Planet MM-21, after their Olympic games this year, curling is getting popular. But the rules are somewhat different from ours. The game is played on an ice game board on which a square mesh is marked. They use only a single stone. The purpose of the game is to lead the stone from the start to the goal with the minimum number of moves.

Fig. 1 shows an example of a game board. Some squares may be occupied with blocks. There are two special squares namely the start and the goal, which are not occupied with blocks. (These two squares are distinct.) Once the stone begins to move, it will proceed until it hits a block. In order to bring the stone to the goal, you may have to stop the stone by hitting it against a block, and throw again.

The movement of the stone obeys the following rules:

At the beginning, the stone stands still at the start square.
The movements of the stone are restricted to x and y directions. Diagonal moves are prohibited.
When the stone stands still, you can make it moving by throwing it. You may throw it to any direction unless it is blocked immediately(Fig. 2(a)).
Once thrown, the stone keeps moving to the same direction until one of the following occurs:
The stone hits a block (Fig. 2(b), (c)).
The stone stops at the square next to the block it hit.
The block disappears.
The stone gets out of the board.
The game ends in failure.
The stone reaches the goal square.
The stone stops there and the game ends in success.
You cannot throw the stone more than 10 times in a game. If the stone does not reach the goal in 10 moves, the game ends in failure.

Under the rules, we would like to know whether the stone at the start can reach the goal and, if yes, the minimum number of moves required.

With the initial configuration shown in Fig. 1, 4 moves are required to bring the stone from the start to the goal. The route is shown in Fig. 3(a). Notice when the stone reaches the goal, the board configuration has changed as in Fig. 3(b).$

这次我就不翻译了，简单的说，你的球在方框里面滚动，注意是滚动不是一格一格地移动，只有遇到障碍才会停止。

有相邻的4个方向可以移动，不能是斜对角等方向。

球如果出界了，则失败；如果滚动了10次以上同样失败。

主要就是这个意思，看看图3就懂了。

思路

这道题和之前有一道一样，都是关于广度优先搜索的，大家可以看看这个：POJ 1979 Red and Black（红与黑）

这里在二维数组中移动的方向和之前的定义一样，图示：

首先需要输入二维数组：

        for (int row = 0; row < H; ++row) {
            for (int col = 0; col < W; ++col) {
                cin >> room[row][col];
            }
        }

找到其中为2的即为起点，将当前的row和col复制相应的起始点（start），然后结束循环。

        // 为2的点为起始点
        for (int row = 0; row < H; ++row) {
            for (int col = 0; col < W; ++col) {
                if (room[row][col] == 2) {
                    sRow = row;
                    sCol = col;
                    break;
                }
            }
        }

因为此时已经不需要这个起始点了，将其重新设置为0，表示可以走。因为有完成的步数要求，所以需要加上一个判断，超过10此输出-1。其中的dfs函数为核心。

        room[sRow][sCol] = 0;
        minStep = 11;
        dfs(sRow, sCol, 0);
        if (minStep > 10) {
            minStep = -1;
        }
        // 输出结果
        cout << minStep << endl;

在dfs函数的开头需要做判断。

    if (step >= 10 || step > minStep) {
        return;
    }

这里的d有4个值，表示4个方向（上、右、下、左），之所以当前的（current）row和col都在for循环开始处，是因为如果走到不能走的地方可以立即返回并重新获得当前（原本）的位置。

    for (int d = 0; d < 4; ++d) {
        int cRow = row;
        int cCol = col;
    }

无论如何都得让点处于该范围之中，其次是判断这个点表示的意思。

while (cRow >= 0 && cRow < H && cCol >= 0 && cCol < W) {
    switch (room[cRow][cCol]) {
    }
}

0表示为空，所以继续往该（d）方向走。

case 0: {
    cRow += direc[d][1];
    cCol += direc[d][0];
    break;
}

3表示为终点，如果step加上当前步骤比之前最小的步数还小，将其赋值给最小步数。

case 3: {
    if (step + 1 < minStep) {
        minStep = step + 1;
    }
    cRow = -1;
    break;
}

1表示为障碍，还原走多的这一步然后进行下一次递归，步数加1，位置还原。

case 1: {
    if (!(cRow - direc[d][1] == row && cCol - direc[d][0] == col)) {
        room[cRow][cCol] = 0;
        dfs(cRow - direc[d][1], cCol - direc[d][0], step + 1);
        room[cRow][cCol] = 1;
    }
    cRow = -1;
    break;
}

默认的情况。

default: {
    break;
}

代码

#include <iostream>
using namespace std;

// 题目中给出的最大宽度和高度
#define MAX_W 20
#define MAX_H 20

// 待输入的宽度和高度以及已走的步数
int W, H;
int step = 0;
int minStep;
int sRow, sCol;

// 待写入的二维数组
int room[MAX_W][MAX_H];
// 顺时针的可走方向
const int direc[4][2] = {
    { 0, -1 },
    { 1,0 },
    { 0, 1 },
    { -1 ,0 },
};

void dfs(const int& row, const int& col, int step) {
    if (step >= 10 || step > minStep) {
        return;
    }
    for (int d = 0; d < 4; ++d) {
        int cRow = row;
        int cCol = col;
        while (cRow >= 0 && cRow < H && cCol >= 0 && cCol < W) {
            switch (room[cRow][cCol]) {
            case 0: {
                cRow += direc[d][1];
                cCol += direc[d][0];
                break;
            }
            case 3: {
                if (step + 1 < minStep) {
                    minStep = step + 1;
                }
                cRow = -1;
                break;
            }
            case 1: {
                if (!(cRow - direc[d][1] == row && cCol - direc[d][0] == col)) {
                    room[cRow][cCol] = 0;
                    dfs(cRow - direc[d][1], cCol - direc[d][0], step + 1);
                    room[cRow][cCol] = 1;
                }
                cRow = -1;
                break;
            }
            default: {
                break;
            }
            }
        }
    }
}

int main()
{
    while (cin >> W >> H, W > 0) {
        // 输入
        for (int row = 0; row < H; ++row) {
            for (int col = 0; col < W; ++col) {
                cin >> room[row][col];
            }
        }
        // 为2的点为起始点
        for (int row = 0; row < H; ++row) {
            for (int col = 0; col < W; ++col) {
                if (room[row][col] == 2) {
                    sRow = row;
                    sCol = col;
                    break;
                }
            }
        }
        room[sRow][sCol] = 0;
        minStep = 11;
        dfs(sRow, sCol, 0);
        if (minStep > 10) {
            minStep = -1;
        }
        // 输出结果
        cout << minStep << endl;
    }
}