題目： UVa - 10653 - Bombs! NO they are Mines!!

題目說明

有一個機器人在地圖上走，地圖上有一些炸彈，給一個起點及終點，求機器人從起點走到終點且繞過炸彈的最短路徑。

Input： 每組測資的第一行為兩整數 R、C，分別表示地圖的寬跟高，若兩者皆為 0 則結束，下面一行為 1 個整數 rows，代表有幾個列有炸彈，接下來 rows 行，每行至少有兩個整數 r、n，分別代表第幾列有炸彈及有幾個炸彈，後面有 n 個數字，表示這一列的哪個位置有炸彈，最後兩行分別代表起始點及終點的位置。

Output： 輸出從起點走到終點的步數。

解題思路

先記錄炸彈的位置，之後 BFS 求解即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <queue>

using namespace std;

// reference: https://ppt.cc/fsckax

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int R, C;
int sx, sy, ex, ey; // 起始點與終點
bool bomb[1005][1005];
bool visited[1005][1005];
int d[] = { 0, 1, 0, -1, 0 }; // 偏移量

int bfs()
{
    queue<pair<int, int>> q;
    q.push({ sx, sy });
    visited[sx][sy] = true;

    int steps = 0;
    while (!q.empty())
    {
        int size = q.size();

        while (size--)
        {
            auto [x, y] = q.front();
            q.pop();

            if (x == ex && y == ey) return steps;

            int dx, dy;
            auto stop = [&] // 不能走的點
            {
                return dx < 0 || dx >= R || dy < 0 
                || dy >= C || visited[dx][dy] || bomb[dx][dy];
            };
            for (int i = 0; i < 4; ++i)
            {
                dx = x + d[i], dy = y + d[i + 1];
                if (stop()) continue;
                q.push({ dx, dy });
                visited[dx][dy] = true;
            }
        }
        ++steps; // 先將目前可能的位置都拓展一步之後再將步數加一
    }
}

int main()
{
    while (cin >> R >> C && !(!R && !C))
    {
        // init
        fill(bomb[0], bomb[0] + 1005 * 1005, false);
        fill(visited[0], visited[0] + 1005 * 1005, false);

        int rows;
        cin >> rows;
        while (rows--)
        {
            int r, n, k;
            cin >> r >> n;
            while (n--) cin >> k, bomb[r][k] = true;
        }

        cin >> sx >> sy >> ex >> ey;
        cout << bfs() << '\n';
    }
}

參考資料

UVa 10653 - Bombs! NO they are Mines!!_小白菜又菜-CSDN博客