LA 3528

From Algorithmist
Jump to navigation Jump to search

LA 3528 - The Warehouse[edit]

Summary[edit]

An agent is locked inside a warehouse (divided into cells) containing several boxes. He may only move in four directions, he may not touch the floor and he wants to reach a given location as quickly as possible. Each box has a given height. In the process of his escape the agent may topple several of the boxes.

Find whether the agent can escape, and if yes, find the shortest possible time.

Explanation[edit]

Basically, all you have to do is a breadth-first search of the state space.

Notes[edit]

The organizers presented a backtracking solution. However, for a grid there may be inputs where a backtracking solution timeouts (see the second example below).

Input[edit]

5 5 3
.2..E
...2.
4....
....4
..2..
8 6 1
E...2...
........
..222222
........
........
22222222
........
..2..2..
0 0 0

Output[edit]

18
Impossible.