UVa 532

From Algorithmist
Jump to navigation Jump to search

532 - Dungeon Master[edit]

Summary[edit]

Given a set of maps which constitute a 3-Dimensional world (a dungeon), determine whether it is possible to travel from the starting cell (marked as 'S') to the ending cell (marked as 'E') and calculate the minimal time-cost for the travelling if possible.

Explanation[edit]

A standard Breadth-First Search would be able to solve the problem.
Consider this adjacency criterion:
Cell B is adjacent to Cell A if and only if we can arrive B from A with one single move.

Gotchas[edit]

  • Be aware of infinite cycles. Mark old cells as 'visited'.
  • To handle the judge input, a queue with large size is needed.
    • Watch out for queue size overflow. DO NOT push redundant elements. Check before you push, not after you pop. Too many elements to be pushed to the queue would result in a TLE with a dynamic-size queue or a RE with a static-size queue.

Notes[edit]

  • As a 3D BFS problem, each cell has 6 possible next move:

{up, down, left, right, previous layer, next layer}
remember to try them all.

Implementations[edit]

Input[edit]

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

1 30 30
.#############################
#...........................E#
#.############################
#.#..........................#
#.#.########################.#
#.#.#......................#.#
#.#.#.####################.#.#
#.#.#.#..................#.#.#
#.#.#.#.################.#.#.#
#.#.#.#.#..............#.#.#.#
#.#.#.#.#.############.#.#.#.#
#.#.#.#.#.#..........#.#.#.#.#
#.#.#.#.#.#.########.#.#.#.#.#
#.#.#.#.#.#.#......#.#.#.#.#.#
#.#.#.#.#.#.#.####.#.#.#.#.#.#
#.#.#.#.#.#.#.##S#.#.#.#.#.#.#
#.#.#.#.#.#.#....#.#.#.#.#.#.#
#.#.#.#.#.#.######.#.#.#.#.#.#
#.#.#.#.#.#........#.#.#.#.#.#
#.#.#.#.#.##########.#.#.#.#.#
#.#.#.#.#............#.#.#.#.#
#.#.#.#.##############.#.#.#.#
#.#.#.#................#.#.#.#
#.#.#.##################.#.#.#
#.#.#....................#.#.#
#.#.######################.#.#
#.#........................#.#
#.##########################.#
#............................#
.#############################

5 10 20
S.##.####.#...##..#.
...#..##.###.#......
#..#.#.#.#.###.###.#
......#.###.###.##.#
####...##..###..##.#
#.##.#..#..#.#.#####
.....#..##..##..#.##
..#.#...#.#.##...##.
..#.###.#..#...#....
###...#.....#.##.##.

#..#.####.#.##.#.##.
..#.....#####.##....
.#.#.#......#..#....
..#.###..#..#####.#.
#.#..##.##..##..#...
...#...####.#..#..#.
######.#.....#.#####
#.##.###.#.###.#.#.#
......#..#.###...#..
###.##.###...#..##..

#...##.......#.#.#.#
.###...##.##..##....
.###.#..##.####.####
.######.....#..##...
#..#.....###...#..#.
.#..######.##......#
.#...#...##.#....#..
###..##......#.####.
#..#...##.#..##...##
#....#######..#.#.##

.......####..##.##..
....##.####....##.##
.#########.#.##...##
#..###.#..###.#...##
##.#.#...###.#...#..
.#.##....#..####...#
.#..###.##.#######..
..##..###.##..####..
.#....#.....##.#.#..
.#.#.#..#...######.#

#....#....#.##..##..
..#..#.#.####.#####.
....###..#....##.###
##...##...#.###.####
.#..#..####.#.####.#
#..##.#.##...#.#..##
.##..#..##.#.###....
##.#..#.##.#..##.##.
####...###.#.#.###.#
#.###...##.##..###.E

0 0 0

Output[edit]

Escaped in 11 minute(s).
Trapped!
Escaped in 418 minute(s).
Escaped in 40 minute(s).