(●—●) |2074 营救 | CODEVS, 算法爱好者社区

2074 营救

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 钻石 Diamond

Pending

总耗时: 0 ms

0 / 0 数据通过测试.

最近的错误点信息

运行结果

错误error

错误信息

题目描述 Description

在一个n*m的一个方块阵阵地上仅由楼房和街道组成，现在你在(x1,y1)点，伤员在(x2,y2)点，你可以向周围的８个方向移动，也可以爬上一部分楼房。而伤员因为受了伤，动弹不得，你必须背他回来。因此你所最担心的不是你的路程长短，而是你在救援中费的力气的大小。你爬上一幢高为Ｈ的楼房，或者从高为Ｈ的楼房房顶下来，都需要花费Ｈ的力气，而没有高度落差的行走是不费力的。现在你要完成救援的任务，最少要花费多少力气呢？费力最小的情况下，你最少又要走多少路呢？这里上、下楼不算走路。

输入描述 Input Description

输入文件的第１行有两个正整数n,m(n,m<=500)，第２，３行分别是(x1,y1),(x2,y2)(1<=x1,x2<=n,1<=y1,y2<=m)。接下来有n行，每行m个数，第I行，第Ｊ列为1表示此处为空地，为2表示此处为房顶，为０表示此处无法攀爬。保证起点，终点不在０上，你可以假设可攀爬的楼房高度都为１。你到了(x2,y2)就表示救援成功。

输出描述 Output Description

输出文件包括两个在一行的数x,y，用一个空格隔开。Ｘ表示费力最少的情况下，路径的最短长度，Ｙ表示最少花费的力气量。若无法完成营救任务，则输出’0 0’（引号不输出）。

样例输入 Sample Input

3 7

1 1

3 7

样例输出 Sample Output

8 4

数据范围及提示 Data Size & Hint

30%的数据满足：n,m<=10

100%的数据满足：n,m<=500

分类标签 Tags 点此展开

广度优先搜索搜索

通过 70

5:5,8:4,12:5,10:6,11:7,12:2,8:6

提交 349

6,5,8,9,6,3,5

20%

通过率

Summary

701 AC
1962 WA
383 TLE
34 MLE
225 RE

本题提交记录