题目描述

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

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

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

当然，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}$ 米不会改变答案。

4 1 100 55 1 1
10 40 60 10

0 1 1 1

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

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

数据范围与提示

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