首页 > ACM题库 > HDU-杭电 > hdu 2445 Little White’s Explore待解决[解题报告]C++
2014
01-26

hdu 2445 Little White’s Explore待解决[解题报告]C++

Little White’s Explore

问题描述 :

Little White likes exploring. One day she finds a maze which has a shape of a rectangle of size n*m. The coordinate of the entrance is (1,1) and the precious deposits are place at (n,m).Except for these two positions, other grids’ height change from time to time. At beginning,they all have the maximum height, and every second their height change by 1(increase or decrease). The grid cannot be stayed on if its height is smaller than min. Little White can jump upwards at most high meters and downwards low meters at a time. Every time, she can choose to go to the adjacent grids(up, down, left or right) or stay at the same grid. There is a lamp at grid (n,m) with height 10. Every time she jumps from i to j, she wishes to see the light of the lamp the moment she gets onto j. Little White has a height 10 and 100 units of power,which decrease by 1 unit for every second. It takes one second for her to jump from one grid to another, and the grids’ height always change after her jump. She will always be at the center of the grids.

输入:

For each data set:
The first line give five integers, n, m, min, high, low(2<=n,m<=35,min>=0,high>=0,low>=0).
The next n lines, each has m integers, indicating the grids’ initial and maximum height.The height of the grid first decreases, then begins to increase when it gets to 0, and then begins to decrease when it gets maximum…

输出:

For each data set:
The first line give five integers, n, m, min, high, low(2<=n,m<=35,min>=0,high>=0,low>=0).
The next n lines, each has m integers, indicating the grids’ initial and maximum height.The height of the grid first decreases, then begins to increase when it gets to 0, and then begins to decrease when it gets maximum…

样例输入:

5 5 0 1 1
18 20 20 20 20
18 20 20 20 20
18 20 18 18 18
18 20 18 20 18
18 18 18 20 7
5 5 7 5 8
23 16 3 2 28
26 8 1 16 19
16 17 26 12 4
30 1 3 3 4
14 4 7 28 12

样例输出:

25
-1

Hint
The rectangle has n rows and m columns. The entrance (1,1) is at the top left corner. She can see the light if it is only blocked by the side of some grids. Both Little White and the lamp are to be considered as points, placed at the center of the grid. Her power must be greater than 0 at any given time during her exploration.


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。