Robot Movement in a Grid Warehouse

A robotics company, Robot Movement Institute (RMI), is testing a robot for transporting goods in a warehouse. The robot is shaped as a sphere of diameter \(1.6\) meters and its center always lies on grid points. The warehouse is modeled as an \(N \times M\) grid where some cells contain obstacles. The robot accepts the following commands, each taking \(1\) second:

• Creep: move forward \(1\) step
• Walk: move forward \(2\) steps
• Run: move forward \(3\) steps
• Left: turn left
• Right: turn right

Given the map of the warehouse and the starting and destination positions (each with a specified facing direction), determine the minimum time required for the robot to complete its task.

Note: The robot can only be positioned at grid points where the corresponding \(2 \times 2\) block of cells (the cell itself and its top and left neighbors) is free of obstacles. The directions are encoded as follows: 1 for east, 2 for west, 3 for south, and 4 for north.

inputFormat

The input consists of several parts:

1. The first line contains two integers \(N\) and \(M\) (\(1 \le N, M \le 100\)), indicating the number of rows and columns of the warehouse grid.
2. The next \(N\) lines each contain \(M\) integers (either 0 or 1), where 0 represents a free cell and 1 represents an obstacle.
3. A line with three integers follows, representing the starting position: row, column, and initial direction.
4. Finally, a line with three integers representing the destination: row, column, and desired facing direction.

Note: In order for the robot to be placed at a grid point, the corresponding \(2 \times 2\) block (i.e. the cell at that position and its immediate top, left, and top-left neighbors) must all be 0. The directions are encoded as follows: 1 for east, 2 for west, 3 for south, and 4 for north.

outputFormat

Output a single integer representing the minimum time (in seconds) required for the robot to complete its task. If it is impossible to complete the task, output -1.

sample

6 6
0 0 0 0 0 0
0 1 1 1 1 0
0 0 0 0 0 0
0 1 1 1 1 0
0 0 0 0 0 0
0 0 0 0 0 0
4 2 3
2 4 1

9