#6407. 「ICPC World Finals 2018」跳过罪恶

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

你的朋友 Robin 是一个超级英雄。你刚注意到这点时,你认为每个人都需要一个爱好,而超级英雄比收集邮票要令人兴奋的多。但现在你很感激家乡里能有一个人对罪恶的行为做些什么。

每晚,Robin 会在屋顶间跳动并观察下面发生了什么,来巡逻这个城市。超级英雄自然要迅速地对罪恶做出反应,因此 Robin 来请你帮助他快速地在家乡移动。

你的家乡建在一个正方形网格上,每个街区的大小是 w \times w 米。每个街区有一个建筑物。建筑物可能有不同的高度(见图)。为了从一个建筑物跳到另一个建筑物(不一定相邻),Robin 会从第一个建筑物的中心跳到第二个建筑物的中心。Robin 无法在空中改变运动方向,但可以选择起跳的角度。

Figure

当然,Robin 希望跳跃时不碰撞到任何建筑物。这种碰撞对于超级英雄来说确实不算什么,但如果有人碰碎玻璃的话,建筑物的主任显然会很不高兴。你向 Robin 解释了跳跃的物理原理:“你的所有跳跃都有相同的初始速度 v ,可以分成朝向目标建筑物的水平速度 v_d 及竖直向上的竖直速度 v_h ,所以 v_d^2 + v_h^2 = v^2 . 在移动过程中,你的水平速度保持不变 (v_d(t) = v_d) ,但你的竖直速度会受到重力影响 (v_h(t)=v_h-t \cdot g) ,在你的家乡, g = 9.80665 m/s. 你的盔甲让你能够忽略空气阻力带来的影响(?)。这使得你能够确定你的飞行路径并...“ 此时你突然发现 Robin 已经打起了瞌睡。

所以这个任务就交给了你:给定城市的布局和 Robin 的秘密据点,你需要判断 Robin 能够到达的建筑物屋顶,以及到达每个屋顶的最小跳跃数。注意如果 Robin 跳跃路径经过了一个建筑物的角落(四个建筑物交会的位置),则 Robin 此时的位置必须同时高于这四个建筑物。

输入格式

输入第一行有六个整数 d_x, d_y, w, v, l_x, l_y ,分别表示城市网格以街区为单位的大小( 1 \le d_x, d_y \le 20 ),每个建筑物以米为单位的宽度( 1 \le w \le 10^3 ),Robin 起跳的初速度 v\ (1\le v\le 10^3) (单位:米每秒),以及 Robin 秘密据点的坐标 ( 1 \le l_x \le d_x,1 \le l_y \le d_y )。 接下来 d_y 行,每行有 d_x 个非负整数。第 j 行表示建筑物 (1,j),(2,j),...,(d_x,j) 的高度。高度均以米为单位,且不超过 10^3

输出格式

输出 Robin 从秘密据点到各建筑物屋顶的最少跳跃次数。如果无法到达,用 X 代替最少跳跃次数。建筑物的输出顺序应与输入一致,共有 d_y 行,每行有 d_x 个数值。你可以假设把任何建筑物的高度增加或减少 10^{-6} 米不会改变答案。

样例

样例输入 1

4 1 100 55 1 1
10 40 60 10

样例输出 1

0 1 1 1

样例输入 2

4 4 100 55 1 1
0 10 20 30
10 20 30 40
20 30 200 50
30 40 50 60

样例输出 2

0 1 1 2
1 1 1 2
1 1 X 2
2 2 2 3

数据范围与提示

在不侵犯原题版权的情况下,本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布,注明出处时需指向本题链接。