配点 : 1800 点
問題文
您和kaage(以下简称“您”), 在N*N 网格上,两个人骑着自行车进行定向运动。从网格顶部开始(0 索引) i 行,从左侧开始(0 索引) 表示为 j 该列中的单元格是 它由 (i,j) 。根据下面所示的定向运动规则,您的目标是在定向运动结束时获得尽可能高的分数。
- 你们是时候了 从 0 到质量 (sx,sy) 出发。
- 定向运动的场地是 这是由0\leq i,j<N 的任意整数 对于 i,j 可以表示为 (i,j) 表示的整个正方形。定向运动期间不能外出。
- 场方格是“陆地”和“海洋” 2 分为类型。当你们在“陆地”广场上时,你们各自,1 你可以垂直、水平或垂直移动到相邻的“陆地”方块,也可以留在原地。你不能进入“海”广场。
- 首先给出您获得“分数”的方式。 目标是完成 M “任务”。使命包括: 3 有不同的类型,如果你完成每一种,你都会收到一个任务。 1 筒木 S_1, S_2, S_3 您可以获得积分。
- 使命 1: 某个方格 两个人同时访问 (x, y) 。 两者之一将访问
- 使命 2: 某个方格 两个人同时访问 (x, y) 。
- 使命 3:一组特定的正方形 两人中的一人将访问 (x_1, y_1),(x_2,y_2),\cdots,(x_k,y_k) 中包含的所有方块。
入力
输入是按以下格式从标准输入给出的。
\(N\) \(T\) \(M\) \(sx\) \(sy\)
\(S_1\) \(S_2\) \(S_3\)
\(v_{0,0}\) \(v_{0,1}\) \(\cdots\) \(v_{0,N-1}\)
\(\vdots\)
\(v_{N-1,0}\) \(v_{N,1}\) \(\cdots\) \(v_{N-1,N-1}\)
Mission_1\\
Mission_2\\
\vdots\\
Mission_M
\(v_{i,j}\) 是 . 或
要么- 。v_{i,j} 是
在 . 当广场 (i,j) 是“土地”,- 的意思是“海”。
另外,Mission_i 代表一个任务,格式如下:
\(1\) \(x_i\) \(y_i\)
使命 1 参观的广场是 (x_i,y_i) 。
\(2\) \(x_i\) \(y_i\)
使命 2 参观的广场是 (x_i,y_i) 。
\(3\) \(k_i\)
\(x_{i,1}\) \(y_{i,1}\)
\(x_{i,2}\) \(y_{i,2}\)
\vdots
\(x_{i,k_i}\) \(y_{i,k_i}\)
使命 3 参观的广场是 (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 分钟后两个人所在的每个方格的位置, i 必须以空格分隔输出。但是,如果你做出了违背题目意图的举动,你这道题的分数将会降低。 0 点,
它变成WA 。举个例子,i 几分钟后您将进入的广场是 (x_{i,A},y_{i,A}), kaage 你所在的方格是 (x_{i,B},y_{i,B}) 时,i 行的输出如下。
除
\(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 ,它们是使用下面所示的算法生成的。 考虑
- N*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|) 。
- 1. 对以下操作求和 50 次。 将
- 2. 对于由以下材料制成的网格 X 当X<30 如果是,请使用“海洋”,否则使用“陆地”。
- 3. 如果创建的网格不满足约束,则返回步骤1。如果满足约束,则该网格成为输出网格。 生成
- M 任务。任务编号是 从 [1,3] 中均匀随机选择,任务 3 的坐标数为 从 [1,5] 中均匀随机选择。坐标是从整个“土地”方格中均匀随机选取的。
採点
您在此问题上的得分是20 测试用例的分数总和为 该值除以 80 并向下舍入到小数点。
入力例1
4 5 2 2 2 7 3 6 .... .... ...- ..-- 3 2 1 2 2 1 2 1 1
出力例1
1 2 2 2 1 1 2 1 2 1 2 1 2 2 2 2 2 2 2 2
请注意,这是一个说明性输入示例,不满足任何约束。 在此示例中,您的分数是 9 变为。
作者: 凯上