数据结构利用二叉树计算路径的长度怎么遍历?采用C语言编程完备的思路?

Problem Description
A small group of commandos has infiltrated deep into enemy territory. They have just accomplished their mission and now have to return to their rendezvous point. Of course they don’t want to get caught even if the mission is already over. Therefore they decide to take the route that will keep them as far away from any enemy base as possible.

Being well prepared for the mission, they have a detailed map of the area which marks all (known) enemy bases, their current position and the rendezvous point. For simplicity, we view the the map as a rectangular grid with integer coordinates (x, y) where 0 ≤ x < X, 0 ≤ y < Y. Furthermore, we approximate movements as horizontal and vertical steps on this grid, so we use Manhattan distance: dist((x1, y1), (x2, y2)) = |x2 − x1| + |y2 − y1|. The commandos can only travel in vertical and horizontal directions at each step.

Can you help them find the best route? Of course, in case that there are multiple routes that keep the same minimum distance to enemy bases, the commandos want to take a shortest route that does so. Furthermore, they don’t want to take a route off their map as it could take them in unknown, dangerous areas, but you don’t have to worry about unknown enemy bases off the map.

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

One line with three positive numbers N, X, Y. 1 ≤ N ≤ 10 000 is the number of enemy bases and 1 ≤ X, Y ≤ 1 000 the size of the map: coordinates x, y are on the map if 0 ≤ x < X, 0 ≤ y < Y.

One line containing two pairs of coordinates xi, yi and xr, yr: the initial position of the commandos and the rendezvous point.

N lines each containing one pair of coordinates x, y of an enemy base.

All pairs of coordinates are on the map and different from each other.

Output
Per testcase:

One line with two numbers separated by one space: the minimum separation from an enemy base and the length of the route.

Sample Input
2
1 2 2
0 0 1 1
0 1
2 5 6
0 0 4 0
2 1
2 3

Sample Output
1 2
2 14

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

相似问题

1
菜鸟#c语言数据结构#二叉树
1
菜鸟#c语言数据结构#二叉树链表
2
为什么根据前序输入可以构造二叉树, 但是知道前序遍历不能确定二叉树? 二者有什么区别?
1
C语言数据结构二叉树-目录树的基本操作求解?
1
前序遍历创建二叉树问题
2
二叉树的基本操作,想三种遍历的基础上想加一个层序遍历
1
数据结构问题:一棵普通的树转化成二叉树,为什么输出的时候无法输出呢(是我转化没有成功吗)?
1
[已解决]94. 二叉树的中序遍历 想用js和栈来实现,但还是报错
1
学习数据结构二叉树的一个问题
3
C++二叉树应用问题求助
1
数据结构java实验四验证教材中树结构的基本操作,设计实现指定操作的算法,并做算法分析。 以下各题二叉树的存储结构是二叉链表表示,方法声明如下: 二叉树的二叉链表结点类:
1
以二叉链表建立二叉树链式存储结构,实现前序遍历、求叶子结点的个数计算、中序遍历、后序遍历、求深度。
1
关于C++二叉树遍历的问题
2
二叉树问题非递归中序遍历
4
二叉树非递归前序遍历
1
编程二叉树求根结点到所有结点的路径长度
1
数据结构求问:想用层次遍历序列构造二叉树,但是下面的代码运行之后只能构造一层,具体应该怎么改?
0
先序建立二叉树中的查找双亲操作
3
求助二叉树一道难题,怎么进行后序遍历输入,要求C语言
1
创建及遍历线索二叉树,出了一些小问题