Infinity Loop - Minimum Rotations to Stop Leaks

The game is played on an \(n \times m\) grid. Each cell contains a pipe piece. There are 15 kinds of pipe pieces. Two of them are straight pipes (a horizontal pipe and a vertical pipe) and cannot be rotated. The remaining 13 pieces can be rotated by 90° (clockwise or counterclockwise, each rotation counts as one move).

Every pipe piece has one or more connection endpoints on its boundaries. Formally, each piece has connections in some of the four directions: up, right, down, and left. When two adjacent cells have connecting endpoints on their common border (i.e. one has a connection toward that side and the other has the connection in the opposite direction), these endpoints are considered to be connected. If a connection endpoint is not connected (because the adjacent cell either does not exist or does not have a matching connection), it is called a leak.

Your task is: given an initial board configuration, determine the minimum number of rotation moves required so that the board has no leaks. If it is impossible to achieve a leak‐free configuration, output -1.

Pipe types and their base connectivity (in the 0° orientation):

• Type 1 (straight, fixed): Horizontal pipe with connections to left and right \((L, R)\).
• Type 2 (straight, fixed): Vertical pipe with connections to up and down \((U, D)\).
• Type 3 (elbow, rotatable): connects up and right \((U, R)\).
• Type 4 (elbow, rotatable): connects right and down \((R, D)\).
• Type 5 (elbow, rotatable): connects down and left \((D, L)\).
• Type 6 (elbow, rotatable): connects left and up \((L, U)\).
• Type 7 (T-shape, rotatable): connects up, right, and down \((U, R, D)\); missing left.
• Type 8 (T-shape, rotatable): connects right, down, and left \((R, D, L)\); missing up.
• Type 9 (T-shape, rotatable): connects down, left, and up \((D, L, U)\); missing right.
• Type 10 (T-shape, rotatable): connects left, up, and right \((L, U, R)\); missing down.
• Type 11 (cross, rotatable): connects in all four directions \((U, R, D, L)\). (Rotation does not change its connectivity.)
• Type 12 (end, rotatable): connects only upward \((U)\).
• Type 13 (end, rotatable): connects only rightward \((R)\).
• Type 14 (end, rotatable): connects only downward \((D)\).
• Type 15 (end, rotatable): connects only leftward \((L)\).

When a rotatable piece is rotated by 90° clockwise, each connection rotates accordingly (e.g. \(U \to R, R \to D, D \to L, L \to U\)). In any cell, if the cell is on a border of the grid, then it must not have any connection pointing outside the grid.

Additionally, for two adjacent cells, the following must hold: the direction of connection on the common edge of one cell should be exactly the opposite of the connection on the neighboring cell. For example, if cell A has a connection to the right, then the cell B to its right must have a connection to the left, and vice versa.

The cost for reorienting a rotatable pipe is defined as the minimum number of 90° rotations needed (in either clockwise or counterclockwise direction) to achieve the chosen orientation from its base (0°) orientation.

Your goal is to compute the minimum total rotation cost needed to achieve a configuration on the board that has no leaks. If no such configuration exists, output -1.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns).

The next \(n\) lines each contain \(m\) integers. The \(j\)-th integer on the \(i\)-th line indicates the type of the pipe in cell \((i, j)\). The types are integers from 1 to 15 as described above.

You may assume that the grid is small enough to allow an exhaustive search (for example, \(n, m \leq 3\) or similar).

outputFormat

Output a single integer representing the minimum total number of rotations required to achieve a leak-free configuration. If it is impossible, output -1.

sample

1 1
12

-1