# LA 3528

## Summary

An agent is locked inside a warehouse (divided into ${\displaystyle N\times N}$ 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

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

## Notes

The organizers presented a backtracking solution. However, for a ${\displaystyle 8\times 8}$ grid there may be inputs where a backtracking solution timeouts (see the second example below).

## Input

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


## Output

18
Impossible.