Moonlit Maze Escape

Minsik is inside a rectangular maze. To escape, he must move onto an exit cell. One move takes him from the current cell to one horizontally or vertically adjacent cell.

Each maze cell is one of the following:

• Empty cell .: always passable.
• Wall #: never passable.
• Key a to f: always passable; the first time Minsik enters the cell, he obtains that key.
• Door A to F: passable only if Minsik has the matching lowercase key.
• Start 0: Minsik's initial position, treated as an empty cell.
• Exit 1: entering this cell escapes the maze.

A key can be reused after it is obtained. Find the minimum number of moves needed for Minsik to reach any exit.

The first line contains the maze height N and width M. (1 <= N, M <= 50)

The next N lines describe the maze. There may be multiple keys or doors of the same type, and a door's matching key might not exist in the maze. There is exactly one 0 and at least one 1. Keys may be used any number of times.

Print the minimum number of moves needed for Minsik to escape the maze. If escape is impossible, print -1.