The warrior will go through a labyrinth to help his princess. There are different kind of
room in the labyrinth. The room may be block or empty. In other case, there are small or
large monster in the room. At first, the warrior can only defeat the small monster but
not large. After kill a certain number of small monsters, the capability of warrior
will upgrade to defeat large monster.
The hero can move up, down, left or right. His objective is to go through the labyrinth
quickly although some monster should be killed. Can you find the best path when the map
of labyrinth is given? Of course, the dead monster can't revive.
The first line of each case are the width and height of maze m,n (m,n <=8), and the integer
k that is the number of monster should be killed to upgrade. At the next m lines, a string
with length n is given to describle the labyrinth. In each string, a letter '.' means empty
room, letter '#' means block room, the lowercase 'o' means small monster and uppercase 'O'
means large monster. The entey of maze is left-top, and the exit is right-bottom.
Output the best step in one line for each case. If there is no route, output -1.
4 4 3
The 2007 ACM-ICPC JiLin Provincial Internet Contest