Toy Maze
The toy maze is a transparent, flat, rectangular box containing obstacles and a moving ball. You can tilt the box in four directions: right, left, towards you, or away from you. After each tilt, the ball rolls in the specified direction until it hits an obstacle or the maze's wall, where it then stops. The objective is to guide the ball into one of the special exit holes. The ball will fall into a hole if it encounters one along its path (it doesn't need to stop directly over the hole).
Initially, the ball is positioned in the upper left corner of the maze. It is guaranteed that there is a solution, and the starting position is neither an obstacle nor a hole.
Input
The first line of the input file contains the integers N and M, representing the dimensions of the maze (positive integers not exceeding 100). Following this, there are N rows, each containing M numbers that describe the maze. In this description, 0 represents a free space, 1 represents an obstacle, and 2 represents a hole.
For example, the maze shown in the image corresponds to the following description:
Output
Output a single number: the minimum number of tilts required for the ball to exit the maze through one of the holes.