Skip to content

LibreOJ - 2633. 宝藏与维京海盗 Treasures and Vikings

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

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

题目描述

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

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

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

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

输入格式

第一行有两个整数 NNMM

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

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

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

输出格式

输出 YESNO,表示是否有一条安全的路径。

输入输出样例

样例输入 #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\% 的数据,1N,M2001 \leq N, M \leq 200
  • 对于 100%100\% 的数据,1N,M7001 \leq N, M \leq 700

思路

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

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

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

代码

#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;
}