Gnome in the Castle

In a rectangular matrix of size N \times M, the layout of an ancient castle is encoded. Each cell of the plan is represented by an integer $A$ (0 \leq A \leq 31), which is formed by the sum of numbers according to the following rules:

• $1$ if there is a wall to the west;

• $2$ if there is a wall to the north;

• $4$ if there is a wall to the east;

• $8$ if there is a wall to the south;

• $16$ if there is a bag of gold in the cell.

An internal wall is shared by two cells. For example, the southern wall of cell $(1,2)$ is also the northern wall of cell $(2,2)$ (see the illustration and the sample input file).

A cell on the boundary without the corresponding outer wall is called an exit cell. The illustration shows two such cells: $(2,1)$ and $(1,5)$. There are at most $10$ exit cells in total.

The gnome is located at the cell with the given coordinates $(i,j)$. He can move to a neighboring cell by crossing a shared side, provided castle walls do not block the way. The gnome can carry exactly one bag of gold (he cannot carry more). What is the minimum number of steps $K$ for the gnome to reach any exit cell while collecting exactly one bag of gold?