迷宫的绕路的一个算法问题,如何运用C语言的程序的编写的方式实现

Problem Description
Alice would like to visit Bob. However, they live in a hilly landscape, and Alice doesn’t like to walk in hills. She has a map of the area, showing the height curves. You have to calculate the total altitude climbed, and the total altitude descended, for the route which minimizes these numbers. It does not matter how far she has to walk to achieve this.

Since you don’t know what the landscape looks like in between the height curves, you cannot know exactly how much climb and descent she will actually get in practice, but you should calculate the minimum possible under optimal conditions based on what you can deduce from the map.

The map is represented as an xy grid. Alice lives in (0, 0), and Bob lives in (100 000, 0). The height curves are represented as polygons, where a polygon cannot intersect itself or another polygon. Furthermore, neither Alice nor Bob lives exactly on a height curve.

Second test case from sample input (compressed).

Input
On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with 0 ≤ N ≤ 2 500, the number of height curves.

One line for each height curve, with 1 ≤ Hi ≤ 1 000 being the height of the curve, 3 ≤ Pi ≤ 2 000 the number of vertices in the polygon, and the vertices x1, y1, …, xPi, yPi having integral values −300 000 ≤ xi, yi ≤ 300 000.

There will be no more than 200 000 polygon vertices in total in all test cases.

Output
Per testcase:

One line with two numbers: the total altitude climbed and the total altitude descended.

Sample Input
2
2
20 3 10 10 0 -10 -10 10
25 3 20 20 0 -20 -20 20
3
100 4 -1 1 1 1 1 -1 -1 -1
300 8 -2 2 2 2 2 -2 5 -2 5 1 6 1 6 -3 -2 -3
50 8 3 3 100001 3 100001 -1 7 -1 7 2 4 2 4 -1 3 -1

Sample Output
5 0
200 250
Source

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
QT 迷宫游戏 可视化迷宫
1
问题 C: 孤岛营救问题【队列 搜索 BFS】。
2
vc++写的一个小球迷宫的小游戏,没有错误,但是无法运行,就是打开后显示exe文件无法运行
2
深度优先搜索,迷宫问题,边长大于7*7就运行不出来。
0
C++迷宫(栈实现),无法回溯
1
用java写的迷宫,能够打开自己制定的迷宫地图,并找出最短路径和遍历迷宫
1
骑士游历C语言版,用类似迷宫算法如下,求大神告知错误的地方。
0
用栈解决迷宫问题不知为什么大的例子跑不出
2
c语言走迷宫问题提问!
1
我有一个代码,能不能帮我把里面的swing和awt改成JavaFx,急需。联系QQ3246798340,可rmb报酬
0
这是我写的迷宫问题的代码,请问各位大神为什么最后输出不了迷宫通路呀
0
用Java做算法提高 学霸的迷宫
0
并查集生成迷宫广度优先搜索最短路径时出现了问题 求大佬解答QAQ很急 拜托了!!!
1
一个数据结构上面路径可达性判断的问题,要求采用C语言技术
0
一个迷宫是否联通的有效性的判定算法怎么实现,采用C语言编程怎么实现
0
蓝桥杯 测试提示运行错误怎么回事呢
1
BFS走迷宫传送门超时怎么改进啊?
0
迷宫的遍历的算法在数据结构方面的一个运用,怎么采用C程序的语言的技术设计的代码实现?
0
c语言,迷宫问题,救救孩子
2
为什么到最后一直无法输出迷宫路径?