Gnome in the Castle
In a rectangular matrix of size N×M, the layout of an ancient castle is encoded. Each cell of the plan is represented by an integer A (0 ≤ A ≤ 31), which is determined by the sum of numbers based on 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 instance, the southern wall of cell (1, 2) is also the northern wall of cell (2, 2) (refer to the illustration and example input file).
A cell on the perimeter without a corresponding outer wall is termed an exit cell. The illustration highlights two such cells: (2, 1) and (1, 5). There are no more than 10 exit cells in total.
A gnome is located in a cell with known coordinates (i, j). He can move to adjacent cells by crossing a shared side, provided there are no obstructing castle walls. What is the minimum number of steps K the gnome needs to reach any exit cell, taking exactly one bag of gold (he cannot carry more)?
Input
The first line contains four numbers: N, M – the dimensions of the matrix (1 ≤ N,M ≤ 50) and i, j – the coordinates of the gnome (1 ≤ i ≤ N, 1 ≤ j ≤ M). The following N lines each contain M numbers, describing the castle plan according to the rules above.
Output
Output a single number – the minimum number of steps K to reach an exit, or -1 if the gnome cannot complete the task.