Skip to content
本博客自 2023 年 4 月 4 日起转为归档状态，可能不再发表新的博文。点此了解博主的竞赛生涯。
This blog has been archived by the owner since April 4, 2023. It may no longer have new updates.

「BalticOI 2011」Treasures and Vikings

题解约 1.2 千字
# 洛谷 # S2OJ # LibreOJ # BalticOI # 2011 # 搜索
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

本题译自 BalticOI 2011 Day1 T4「Treasures and Vikings」。

#题目描述

你有一张藏宝图，藏宝图可视为 N×MN \times M 的网格。每个格子可能是你的船、贼船、海、陆地或藏宝点。你只有一条船，整张图只有一条贼船。你和贼船都只能在海域移动。藏宝点在海中。

你与贼船交替移动，你移动一次 + 贼船移动一次算作一回合。每次移动，你可以移动到上下左右四个相邻格子中的一格，也可以不移动。贼船的移动同理，贼船也可以不移动。你先移动。

每一回合结束后，如果你和贼船在同一行或同一列，你就挂了；在你没挂的情况下，如果你位于藏宝点，你就拿到了宝藏。

请问：是否有一条安全的路径，使得无论贼船怎么跑你都能或者拿到宝藏。

#输入格式

第一行有两个整数 NN 和 MM。

在接下来的 NN 行中，每行 MM 个字符。字符的含义如下：

字符 . I V Y T
含义 海 陆地 贼船 你 藏宝点

保证只会出现表中的五种字符，保证 V, Y, T 都只出现一次。

#输出格式

输出 YES 或 NO，表示是否有一条安全的路径。

#输入输出样例

样例输入 #1

5 7
Y.....V
..I....
..IIIII
.......
...T...

样例输出 #1

YES

样例输入 #2

5 7
Y....V.
..I....
..IIIII
.......
...T...

样例输出 #2

NO

样例输入 #3

2 3
.YT
VII

样例输出 #3

NO

#数据范围与约定

  • 对于 50%50\% 的数据，1≤N,M≤2001 \leq N, M \leq 200 。
  • 对于 100%100\% 的数据，1≤N,M≤7001 \leq N, M \leq 700 。

#思路

先使用广搜预处理一下贼船到达每个非陆地点的最小时间并存储下来，然后再使用广搜搜一下是否能到 T 点即可。

在第二遍广搜的时候需要注意，如果到达某个点的用时比贼船到达的用时长，那么这条路就是走不通的，不能扩展。

其余信息可以看代码注释.

#代码

C++
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>

using namespace std;

const int to[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int n, m, book[705][705];
bool vis[705][705];
char g[705][705];
pair<int, int> y, v, t;

struct node {
    int x, y, step;

    node()
        : x(0), y(0), step(0) {}
    node(int _x, int _y)
        : x(_x), y(_y), step(0) {}
    node(pair<int, int> _point)
        : x(_point.first), y(_point.second), step(0) {}
    node(pair<int, int> _point, int _step)
        : x(_point.first), y(_point.second), step(_step) {}
    node(int _x, int _y, int _step)
        : x(_x), y(_y), step(_step) {}
};

/**
 * @brief Preprocess the map
 */
void bfsV() {
    memset(vis, 0x00, sizeof(vis));
    memset(book, 0xff, sizeof(book));
    queue<node> q;
    q.push(v);
    vis[v.first][v.second] = true;
    book[v.first][v.second] = 0;
    while (!q.empty()) {
        int now;
        auto u = q.front();
        q.pop();

        // Top
        now = u.x - 1;
        while (now >= 0 && g[now][u.y] != 'I') {
            if (book[now][u.y] == -1) {
                book[now][u.y] = u.step;
            }
            now--;
        }

        // Bottom
        now = u.x + 1;
        while (now < n && g[now][u.y] != 'I') {
            if (book[now][u.y] == -1) {
                book[now][u.y] = u.step;
            }
            now++;
        }

        // Left
        now = u.y - 1;
        while (now >= 0 && g[u.x][now] != 'I') {
            if (book[u.x][now] == -1) {
                book[u.x][now] = u.step;
            }
            --now;
        }

        // Right
        now = u.y + 1;
        while (now < m && g[u.x][now] != 'I') {
            if (book[u.x][now] == -1) {
                book[u.x][now] = u.step;
            }
            now++;
        }

        // Expand
        for (int i = 0; i < 4; i++) {
            node e = node(u.x + to[i][0], u.y + to[i][1], u.step + 1);
            if (e.x >= 0 && e.x < n && e.y >= 0 && e.y < m && g[e.x][e.y] != 'I' && !vis[e.x][e.y]) {
                vis[e.x][e.y] = true;
                q.push(e);
            }
        }
    }
}

/**
 * @brief Search path to treasure
 */
void bfsY() {
    memset(vis, 0x00, sizeof(vis));
    queue<node> q;
    q.push(node(y, 1));
    while (!q.empty()) {
        auto u = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            node e = node(u.x + to[i][0], u.y + to[i][1], u.step + 1);
            if (e.x >= 0 && e.x < n && e.y >= 0 && e.y < m && e.step <= book[e.x][e.y] && !vis[e.x][e.y]) {
                vis[e.x][e.y] = true;
                // Reached
                if (e.x == t.first && e.y == t.second) {
                    cout << "YES" << endl;
                    return;
                }
                // Expand
                q.push(e);
            }
        }
    }
    // Can't reach treasure
    cout << "NO" << endl;
}

int main() {
    // Read from stdin
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }
    // Mark you, viking and treasure
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'Y') y = make_pair(i, j);
            if (g[i][j] == 'V') v = make_pair(i, j);
            if (g[i][j] == 'T') t = make_pair(i, j);
        }
    }
    bfsV();
    bfsY();
    return 0;
}