题目来源: 2023 ICPC 陕西省赛: J. Teleport

题面

在 \(n\times n\) 的网格中, 有些格点可以通过 (用.表示), 有些格点不可通过 (用*表示). 你需要从 \((1,1)\) 移动到 \((n,n)\). 保证 \((1,1)\) 和 \((n,n)\) 两个点是可以通过的.

当你在 \((x,y)\) 时, 你可以在一个单位时间内移动到以下点中的一个:

  1. \((x+1,y)\) 或 \((x-1,y)\) 或 \((x,y+1)\) 或 \((x,y-1)\);

  2. \(f^i(x,y)\), 其中 \(i\) 是任意的整数 \(i\le k\).

不能移动到不可通过的点或者地图外的点. \(f^i(x,y)\) 的定义为: \[ f^i(x,y)=\begin{cases}(x,y)&i=0\\f^{i-1}(y+1,x)&i>0\end{cases} \] 求从 \((1,1)\) 移动到 \((n,n)\) 的最短时间, 无解输出 -1.

数据范围

\[ 1\le n,k\le5000 \]

题解

对于题面给出的两种移动方式, 总共有 \(4+k\) 种可能到达的点, 直接进行 BFS 复杂度为 \(O(n^2k)\), 不能接受.

现将两种移动方式分开处理, 移动方式 1 是普通移动, 移动方式 2 是空間移動テレポート. 其中普通移动有 \(4\) 条路可以走, 空间移动有 \(k\) 条路可以走.

注意到, 在 BFS 过程中, 如果 \(f^i(x,y)\) 点已经因空间移动而被 BFS 过, 则从 \(f^j(x,y)\) 开始进行 BFS 时, \(f^{1}(x,y),f^2(x,y),\cdots,f^{i-j}(x,y)\) 均已经因空间移动而被 BFS 过, 不需要再考虑到这些点的空间移动, 只需要考虑 \(i-j\) 阶之后的 Teleport 即可. 根据这一特性, 每一个点至多被空间移动到一次. 复杂度为 \(O(n^2)\).

需要注意的是, 本题的空间上限为 256 MiB, 在进行 BFS 的过程中, 队列需要 \(3n^2\) 大小的数组, 如果采用 int 数组, 则需要 286 MiB 的内存. 因此需要关注空间使用情况: 使用 short 数组或使用 STL std::queue.

代码实现

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> point;

int n, k;

bool bfsed[5003][5003];
bool teled[5003][5003];
bool pass[5003][5003];

point teleport(int x, int y, int k)
{
    int hk = k >> 1;
    if (k & 1)
        return {y + hk + 1, x + hk};
    return {x + hk, y + hk};
}

void add_bfs(int x, int y, int depth, queue<pair<point, int>> &bfs)
{
    if (!bfsed[x][y] && pass[x][y])
    {
        bfsed[x][y] = true;
        bfs.push({{x, y}, depth});
    }
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            char sym;
            cin >> sym;
            if (sym == '.')
                pass[i][j] = true;
            else
                pass[i][j] = false;
        }
    queue<pair<point, int>> bfs;
    add_bfs(1, 1, 0, bfs);
    int ans = -1;
    while (!bfs.empty())
    {
        point np = bfs.front().first;
        int dep = bfs.front().second;
        bfs.pop();
        
        int x = np.first, y = np.second;
        if (x == n && y == n)
        {
            ans = dep;
            break;
        }
        int maxk = min(min(2 * (n - x) + 1, 2 * (n - y)), min(n + n - x - y, k));
        for (int i = maxk; i > 0; --i)
        {
            point tp = teleport(x, y, i);
            int tx = tp.first, ty = tp.second;
            if (teled[tx][ty])
                break;
            teled[tx][ty] = true;
            add_bfs(tx, ty, dep + 1, bfs);
        }
        add_bfs(x + 1, y, dep + 1, bfs);
        add_bfs(x - 1, y, dep + 1, bfs);
        add_bfs(x, y + 1, dep + 1, bfs);
        add_bfs(x, y - 1, dep + 1, bfs);
    }
    cout << ans;
}