3488: 定向越野-【2014暑期训练】T5Day2T3

定向越野

【问题描述】

交大闵行校区位于上海西南处，离市中心距离略远，因此占地面积巨大，足有5000 亩之多， 校园周长达8 公里，因而校团委学生会充分利用了资源，每年都要在校园里举办定向越野比赛， 但规则与普通定向越野不同，每个队被要求从某个起点出发最后到达终点，只要是地图上每个被标注的点都可以走，经过一个点时必须在打卡器上打卡作记录，记录该点的打卡器所在位置的海拔高度，高度用一个非负整数来量度，该数将会被所保存在卡中。最后到达终点时，该队 的成绩就为卡中记录的最大数与最小数之差，差最小的队伍将摘取桂冠。

    ZZ 和他的同学也参与了这项运动，拿到地图后，他们想要迅 找到一条最佳路线以确保获得冠军。

    PS：其实光脑子好能算出最佳路线还不够，还得能跑，但我们假设ZZ                            他们队个个都是 SUPERMAN，只要你帮助他们找到了最佳路线，他们就能获得冠军。

【文件输入】

数据的第一行包含一个正整数n，表示校园地图上共有n*n 个被标注的点（n≤100）

   接下来n 行每行有n 个非负整数aij，表示该点的打卡器所在位置的高度。（aij ≤200） 。                     

    ZZ 和他的同学从(1,1)出发，目的地为(n,n)。

【文件输出】

文件包含一个整数，即最小的高度差的值

【输入样例】

5

1 1 3 6 8

1 2 2 5 5                      

4 4 0 3 3

8 0 2 2 4

4 3 0 3 1

【输出样例】

3

【数据规模】

对于40%的数据，保证N ≤20

对于100%的数据，保证N ≤100

二分
如果知道了路上的最大值和最小值，只要跑一遍bfs就可以了
如果枚举最大值和最小值，显然是会超时的。
注意到，当最小值确定时，最大值越大，这个图越容易联通
所以二分最大值，就可以了
复杂度为200*n*n*log200


不二分
当确定了最小值以后，就变成了联通性问题，可以用并查集来解决
随着最大值的变大，图中能经过的点（avaliable）只增不减
用并查集把新增的点加入即可，然后判断是否联通，就不用bfs了
复杂度200*n*n，比二分还好