2 shunfurh shunfurh 于 2017.09.03 08:54 提问

Direct Visibility

Problem Description
Building the GSM network is a very expensive and complex task. Moreover, after the Base Transceiver Stations (BTS) are built and working, we need to perform many various measurements to determine the state of the network, and propose effective improvements to be made.
The ACM technicians have a special equipment for measuring the strength of electro-magnetic fields, the transceivers' power and quality of the signal. This equipment is packed into a huge knapsack and the technician must move with it from one BTS to another. Unfortunately, the knapsack have not enough memory for storing all of the measured values. It has a small cache only, that can store values for several seconds. Then the values must be transmitted to the BTS by an infrared connection (IRDA). The IRDA needs direct visibility between the technician and the BTS.

Your task is to find the path between two neighbouring BTSes such that at least one of those BTSes is always visible.

Input
There is a single positive integer T on the first line of input. It stands for the number of test cases to follow. Each test case consists of a town description. For simplicity, a town is modelled as a rectangular grid of P x Q square fields. Each field is exactly 1 metre wide. For each field, a non-negative integer Zi,j is given, representing the height of the terrain in that place, in metres. That means the town model is made of cubes, each of them being either solid or empty. There are no "half solid" cubes.

The first line of each test case contains two integer numbers P and Q, separated by a single space, 1 <= P, Q <= 200. Then there are P lines each containing Q integer numbers separated by a space. These numbers are Zi,j, where 1 <= i <= P, 1 <= j <= Q and 0 <= Zi,j <= 5000. After the terrain description, there are four numbers R1, C1, R2, C2 on the last line of each test case. These numbers represent position of two BTSes, 1 <= R1, R2 <= P, 1 <= C1, C2 <= Q. The first coordinate (R) determines the row of the town, the second coordinate determines the column.

The technician is moving in steps (steps stands for Standard Technician's Elementary Positional Shift). Each step is made between two neighbouring square fields. That means the step is always in North, South, West or East direction. It is not possible to move diagonally. The step between two fields A and B (step from A to B) is allowed only if the height of the terrain in the field B is not very different from the height in the field A. The technician can climb at most 1 metre up or descend at most 3 metres down in a single step.

At the end of each step, at least one of the two BTSes must be visible. However, there can be some point "in the middle of the step" where no BTS is visible. This is OK and the data is handled by the cache. The BTS is considered visible, if there is a direct visibility between the unit cube just above the terrain on the BTSes coordinates and the cube just above the terrain on the square field, where the technician is. Direct visibility between two cubes means that the line connecting the centres of the two cubes does not intersect any solid cube. However, the line can touch any number of solid cubes. In other words, consider both the BTS and the technician being points exactly half metre above the surface and in the centre of the appropriate square field.

Note that the IRDA beam can go between two cubes that touch each other by their edge, although there is no space between them. It is because such a beam touches both of these two cubes but does not intersect any of them. See the last test case of the sample input for an example of such a situation.

Output
You are to find the shortest possible path meeting the above criteria. All steps must be done between neighbouring fields, the terrain must not elevate or descend too much, and at the end of each step, at least one BTS must be visible.

For each test case, print one line containing the sentence The shortest path is M steps long., where M is the number of steps that must be made. If there is no such path, output the sentence Mission impossible!.

Sample Input
4
5 5
8 7 6 5 4
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
1 1 5 1
5 8
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
9 9 9 9 9 9 9 2
2 2 2 2 2 2 2 2
1 2 5 1
5 8
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
9 9 9 9 9 9 9 2
2 2 2 2 2 2 2 2
1 5 5 1
6 12
5 5 5 5 1 5 5 5 5 5 5 5
5 5 5 5 1 5 5 5 5 5 5 5
5 5 5 5 9 5 5 5 5 5 5 5
5 9 1 5 5 5 5 5 5 5 5 5
5 5 9 5 5 5 5 5 5 5 5 5
5 5 9 5 5 5 5 5 5 5 5 5
6 1 3 12

Sample Output
The shortest path is 10 steps long.
Mission impossible!
The shortest path is 14 steps long.
The shortest path is 18 steps long.

2个回答

caozhy
caozhy   Ds   Rxr 2017.09.17 22:42
已采纳
Runner__1
Runner__1   Rxr 2017.09.03 09:07
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
杭电OJ分类题目(2)
原题出处:HDOJ Problem Index by Type,http://acm.hdu.edu.cn/typeclass.php杭电OJ分类题目(2)HDU Water~~~HDU 1004 Let the Balloon RiseHDU 1005 Number SequenceHDU 1008 ElevatorHDU 1012 u Calculate eHDU 1013 Digital R...
Linux下__attribute__((visibility ("default")))的使用
Linux下__attribute__((visibility ("default")))的使用
GCC系列: __attribute__((visibility("")))
在 objc-api.h 里面有很多关于__attribute__ 的. 例如 #if !defined(OBJC_VISIBLE) # if TARGET_OS_WIN32 # if defined(BUILDING_OBJC) # define OBJC_VISIBLE __declspec(dllexport) # else #
Android中visibility属性
Android开发中,大部分控件都有visibility这个属性,其属性有3个分别为“visible ”、“invisible”、“gone”。主要用来设置控制控件的显示和隐藏。 1) 可见(visible) XML文件:android:visibility="visible" Java代码:view.setVisibility(View.VISIBLE); 2) 不可见(invi
jquery 设置 visibility 属性
if($("#zj").css("visibility")!="hidden"){ $("#zj").css("visibility","hidden"); }else{ $("#zj").css("visibility","visible"); };
js中 visibility和display的区别
大多数人很容易将CSS属性display和visibility混淆,它们看似没有什么不同,其实它们的差别却是很大的。 visibility属性用来确定元素是显示还是隐藏,这用visibility="visible|hidden"来表示,visible表示显示,hidden表示隐藏。当visibility被设置为"hidden"的时候,元素虽然被隐藏了,但它仍然占据它原来所在的位置。例:
#495 – 绑定Visibility 属性不需要转换器类(Binding to a Visibility Property Without Using a Value Converter)
在绑定Visibility属性的时候,你可以使用一个转换器converter将string类型转换为System.Windows.Visibility 类型。你也可以直接将string类型设置给Visibility 属性,不需要转换器。 下面的例子中。我们绑定选中的ComboBoxItem的Content 属性。Content 里面包含的是字符串,绑定的过程中不需要转换转换器。
GCC扩展 __attribute__ ((visibility("hidden")))
http://liulixiaoyao.blog.51cto.com/1361095/814329
define AB_EXTERN extern "C" __attribute__((visibility ("default")))
#ifndef AddressBook_AddressBookDefines_h  //如果没有定义这个头文件 #define AddressBook_AddressBookDefines_h  //接下来就定义这个文件, #ifdef __cplusplus //是c++的意思,判断是不是c++语言     #define AB_EXTERN extern "C" __attrib
java-Cannot reduce the visibility of the inherited method from 父类
 2014-07-17 10:38 by SchrodingerCat