h******r
发帖数: 201 | 1 这个题目应该是很经典的，可惜我一天都没弄出来。谢谢大牛们
The Prince of Persia has been thrown onto the top level of Jaffar's
underground labyrinth. The labyrinth consists of h levels strictly on top of
each other. Each level is split into m by n areas. Some areas have columns
that support ceiling, some areas are free. The Prince can move only to free
areas. To move to the level below the Prince can break the floor underneath
him and jump down if there is no column underneath. Every move takes the
Prince 5 seconds. A Princess is waiting for the Prince at the lowest level.
Write a program that will help the Prince to save the Princess as fast as
possible by finding the shortest path between them and outputting time it
took the Prince to find the Princess. The structure of the labyrinth is
given bellow. The Prince’s location is marked with '1', the Princess’s
location is marked with '2'. ‘.’ - marks a free spot and ‘o’ marks a
column.
1 . .
o o .
. . .
o o o
. . o
. o o
o o o
o . .
o . 2 | l*****u
发帖数: 13 | 2 Dijkstra's algorithm in 3D Cube...
Dijkstra in 2D grid在一个点上下左右BFS，in 3D cube要做上下左右+下一层的BFS |
|
