AT_pakencamp_2020_day2_h 旅立ちの日に
题目描述
你和 kaage 君（下称「你们」）正在一个 $N \times N$ 的网格上进行自行车定向越野活动。网格中的一个位置用 $(i, j)$ 表示，这里 $i$ 是从上到下的行编号（0 开始），$j$ 是从左到右的列编号（0 开始）。你们的目标是在遵循以下定向越野规则的前提下，尽可能获得更高的「得分」。
- 你们从时刻 0 起，位于位置 $(sx, sy)$。
- 定向越野的活动场地是由所有满足 $0 \leq i, j < N$ 的整数 $i, j$ 构成的网格。在活动过程中，你们不能离开这个区域。
- 网格中的每个位置可以是「陆地」或「海洋」。当你们位于「陆地」位置时，每个人可以在 1 分钟内移动到相邻的上下左右的「陆地」位置，或选择留在原地。「海洋」位置无法进入。
- 通过完成初始给定的 $M$ 个「任务」，你们可以获得「得分」。任务分为以下三种类型，完成后可分别获得 $S_1, S_2, S_3$ 点的得分：
1. 任务 1：两人同时访问某个位置 $(x, y)$。
2. 任务 2：两人中的任意一人访问某个位置 $(x, y)$。
3. 任务 3：两人中的任意一人访问一个位置集合中的所有位置 $(x_1, y_1), (x_2, y_2), \cdots, (x_k, y_k)$。
输入格式
输入通过标准输入给出，格式如下：
```
N T M sx sy S1 S2 S3
v_{0,0} v_{0,1} ... v_{0,N-1}
...
v_{N-1,0} v_{N-1,1} ... v_{N-1,N-1}
Mission_1
Mission_2
...
Mission_M
```
- 其中，$v_{i,j}$ 可以是 `.` 或 `-`。若 $v_{i,j}$ 为 `.`，表示位置 $(i, j)$ 是「陆地」，若为 `-`，表示该位置是「海洋」。
- 每个 $Mission_i$ 表示一个任务，格式如下：
- 任务 1：
```
1 x_i y_i
```
目标位置为 $(x_i, y_i)$。
- 任务 2：
```
2 x_i y_i
```
目标位置为 $(x_i, y_i)$。
- 任务 3：
```
3 k_i x_{i,1} y_{i,1} x_{i,2} y_{i,2} ... x_{i,k_i} y_{i,k_i}
```
目标位置为 $(x_{i,1}, y_{i,1}), (x_{i,2}, y_{i,2}), \cdots, (x_{i,k_i}, y_{i,k_i})$。
输出格式
在定向越野过程中，对于每一个 $1 \leq i \leq T$，你需要输出在第 $i$ 分钟时，两人的当前位置。每行输出格式为四个用空格分隔的整数，依次是你的位置 $(x_{i,A}, y_{i,A})$ 和 kaage 君的位置 $(x_{i,B}, y_{i,B})$。如果你们进行了不符合规则的移动，所得的得分会被记为 0，并会得到 `WA` 提示。例如，第 $i$ 分钟时你在 $(x_{i,A}, y_{i,A})$，kaage 君在 $(x_{i,B}, y_{i,B})$，应输出为：
```
x_{i,A} y_{i,A} x_{i,B} y_{i,B}
```
说明/提示
### 约束条件
- 除 $v_{i,j}$ 外，所有输入均为整数。
- $N = 201$
- $sx = sy = 100$
- $T = 10000$
- $M = 1000$
- $S_1 = 5, S_2 = 4, S_3 = 7$
- $v_{i,j}$ 是 `.` 或 `-` 之一。
- $1 \leq k_i \leq 5$
- $0 \leq x_i, x_{i,j}, y_i, y_{i,j} \leq 200$
- 位置 $(x_i, y_i), (x_{i,j}, y_{i,j}), (sx, sy)$ 均为「陆地」。
- 从 $(sx, sy)$ 出发，经过「海洋」以外的位置可以到达所有其他「陆地」。
- 网格中的「陆地」占比至少一半。
### 测试用例生成方法
共有 20 个测试用例，按以下流程生成：
1. 创建一个 $N \times N$ 的网格。从区间 $[0, N)$ 中随机选择 $x_i, y_i$，从区间 $[0, 70]$ 中随机选择 $h_i$，并在网格中建立一个以 $(x, y)$ 为中心、高为 $h_i$ 的山。具体地，在位置 $(x, y)$ 加上 $max(0, h_i - |x_i - x| - |y_i - y|)$。
2. 重复上述步骤 50 次。
3. 对于生成的网格，比较某个位置的值与阈值 $X$，若该位置的值小于 $X$，则属于「海洋」，否则为「陆地」。
4. 若生成的网格不符合同上述约束，则重回步骤 1，否则输出网格即为题目的输出。
5. 生成 $M$ 个任务。任务的类型从 1 至 3 随机选取，任务 3 的坐标数量从 1 至 5 随机选取，坐标从「陆地」中随机选取。
测试用例的最终得分为所有测试用例得分的总和除以 80 并向下取整后的结果。
**本翻译由 AI 自动生成**