UVa 589

From Algorithmist
Jump to: navigation, search

589 - Pushing Boxes[edit]

Summary[edit]

This is a shortest path problem, with the location pairs (<x,y>,<x,y>) of ( person, box ) as vertices, and the shortest way such that box is in the end.

Explanation[edit]

A person 'P' pushes a box 'B' to a target 'T' in a rectangular maze which consist of empty cell '.' and blocked cell '#'. This problem can be solved using Dijkstra's Algorithm with the box 'B' as the single source. In generating the adjacent nodes around the box 'B', another (nested) Dijkstra's algorithm is needed to verify whether the person 'P' can reach behind the box 'B' to push it in certain direction to the adjacent nodes of the box 'B' (North/East/South/West). When generates the adjacent nodes, the parent of that node is saved for printing the path at the end.

Gotcha's[edit]

  • The box 'B' may be pushed to a cell and leave the cell and later on pushed on the same cell again. This is the case:
2 5
TSB..
##...

Because of this possibility, the parent to determine the path should be stored on the generated node and that node should not be deleted until the dijkstra ended or until the path has been generated.

  • Forgot to minimize the number of pushes. However, forgot to minimze the number of walks is OK since the judge doesn't have the test data for that yet.

Implementation[edit]

The best implementation is using STL vector instead of queue for the Dijkstra's algorithm. Since we don't want do discard the node by calling Q.pop(). All generated nodes should be available when printing the path from the target 'T'. The reason is the Gotcha's #1.

For the second Dijkstra, its just a regular Dijkstra and for printing the person path (the walks) can be reproduced when printing the box 'B' path for the first Dijkstra.

Input[edit]

1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0

Output[edit]

Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS