题目描述

Your friend Robin is a superhero. When you first found out about this, you figured everybody needs a hobby, and this seems more exciting than stamp collecting, but now you are really thankful that somebody is doing something about the crime in your hometown.

Every night, Robin patrols the city by jumping from roof to roof and watching what goes on below. Naturally, superheroes need to respond to crises immediately, so Robin asked you for help in figuring out how to get around your hometown quickly.

Your hometown is built on a square grid, where each block is $w \times w$ meters. Each block is filled by a single building. The buildings may have different heights (see Figure E.1) . To get from one building to another (not necessarily adjacent) building, Robin makes a single jump from the center of the roof of the first building to the center of the roof of the second building. Robin cannot change direction while in the air, but can choose the angle at which to lift off.

Figure E.1 : Cross-section of buildings corresponding to the first sample input. Buildings are shown in black, and the jump from the roof at $(1 , 1)$ to the roof at $(4 , 1)$ is shown with a green line.

Of course, Robin only wants to perform jumps without colliding with any buildings. Such collisions do little damage to a superhero, but building owners tend to get irritated when someone crashes through their windows. You explain the physics to Robin: All your jumps are done with the same initial velocity $v$ , which has a horizontal component $v_{d}$ towards the destination and vertical component $v_{h}$ upwards, so $v_{d}^{2} + v_{h}^{2} = v^{2}$ . As you travel, your horizontal velocity stays constant $(v_{d}(t) = v_{d}),$ but your vertical velocity is affected by gravity $(v_{h}(t) = v_{h} − t · g)$ , where $g = 9$ . $80665 m/s^{2}$ in your hometown. Naturally, your cape allows you to ignore the effects of air resistance. This allows you to determine your flight path and $ \cdots $ at which point you notice that Robin has nodded off $-$ less math, more super-heroing!

So it falls to you: given a layout of the city and the location of Robin's secret hideout, you need to determine which building roofs Robin can reach, and the minimum number of jumps it takes to get to each roof.

Note that if Robin's jump passes over the corner of a building (where four buildings meet), then the jump needs to be higher than all four adjacent buildings.

$$

输入格式

The input starts with a line containing six integers $d_{x}, d_{y}, w , v , ℓ_{x}, ℓ_{y}.$ These represent the size $d_{x} \times d_{y}$ of the city grid $(1 \le d_{x}, d_{y} \le 20)$ in blocks, the width of each building $(1 \le w \le 10^{3})$ in meters, Robin's takeoff velocity $(1 \le v \le 10^{3})$ in meters per second, and the coordinates $(ℓ_{x}, ℓ_{y})$ of Robin's secret hideout $(1 \le ℓ_{x} \le d_{x}, 1 \le ℓ_{y} \le d_{y}).$

The first line is followed by a description of the heights of the buildings in the city grid. The description consists of $d_{y}$ lines, each containing $d_{x}$ non-negative integers. The $j^{th}$ line contains the heights for buildings $(1 , j),(2 , j)$ , . . . $,(d_{x}, j)$ . All heights are given in meters and are at most $10^{3}.$

输出格式

Display the minimum number of jumps Robin needs to get from the secret hideout to the roof of each building. If there is no way to reach a building's roof, display $X$ instead of the number of jumps. Display the buildings in the same order as given in the input file, split into $d_{y}$ lines, each containing $d_{x}$ values.

You may assume that changing the height of any building by up to $10^{−6}$ would not change the answers.

题目大意

题目描述

你的朋友罗宾（Robin）是一位超级英雄。当你第一次发现这个事时，你认为“每个人都需要有爱好，这个看起来比收集邮票有意思多了”，但是现在你十分感谢那些在你的家乡胡作非为的人。

每个晚上， 罗宾（Robin）用在房顶上跳跃的方式巡逻整座城市，并且看下面发生了什么。自然，超级英雄需要立即应对危机，所以罗宾（Robin）寻求你的帮助，帮他找出如何迅速走遍你的家乡。

你的家乡建立在一个方形的格子上，其中每个区块有 $w\times w$ 米。每个区块是一个独立的建筑，建筑有可能有不同的高度,为了从一个建筑到另一个（不一定相邻的）建筑，罗宾（Robin）从第一个房屋屋顶的中间跳到第二个房屋屋顶的中间。不能在空中改变方向，但可以选择起飞的角度。

当然，罗宾（Robin）不想撞到任何一个建筑。一些碰撞很难对超级英雄造成伤害，但是当有人击穿房屋主人的窗户时，他们容易感到生气。你向罗宾（Robin）解释物理学：“你的每次跳都有一个初速度$v$，可以被分解成一个向前的水平分力$v_d$和一个向上的竖直分力$v_h$，且$v_{d}^{2} + v_{h}^{2} = v^{2}$.当你行动时，你的水平分力保持不变$(v_{dt} = v_{d}),$，但是竖直分力受到重力的影响$(v_{h}(t) = v_{h} − t · g)$，设在你的家乡重力加速度$g=9.80665$。自然，你的斗篷可以让你忽略空气阻力的影响。这可以让你确定你的飞行路线和……”这是你注意到罗宾（Robin）已经睡着了-少一点数学，多一点超级英雄！

所以现在轮到你了：已经给出城市的布局和罗宾（Robin）秘密藏身处的位置，你需要确定罗宾（Robin）能到达哪些屋顶并给出最少跳跃次数。

请注意，如果罗宾（Robin）的跳跃经过一栋建筑的角落（四栋建筑交汇的地方），那么跳跃需要比所有四栋相邻建筑都高。

输入格式

输入的第一行包含六个整数$d_x$,$d_y$,$w$,$v$,$l_x$,$l_x$.这些代表了 $d_x\times d_y$ 的城市面积（单位：区块）$(1 \le d_{x}, d_{y} \le 20)$，每座建筑的宽度$(1 \le w \le 10^{3})$，罗宾（Robin）的起跳速度$(1 \le v \le 10^{3})$（单位：米每秒），和罗宾（Robin）藏身处的坐标$(1 \le ℓ_{x} \le d_{x}, 1 \le ℓ_{y} \le d_{y}).$。

第一行后面是对城市网格中建筑高度的描述。描述由$d_y$行组成，每个行包含$d_{x}$个非负整数。第j行包含建筑物$(1 , j),(2 , j)$ , . . . $,(d_{x}, j)$ 的高度（单位：米）。高度最高不超过$10^3$米。

输出格式

输出罗宾从秘密藏身处跳到每栋建筑屋顶所需的最小跳跃次数。如果无法到达建筑物的屋顶，则显示$X$而不是跳跃次数。按输入文件中给定的顺序显示建筑，分为$d_{y}$行，每行包含$d_{x}$个值。

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

提示

Time limit: 2 s, Memory limit: 1024 MB.