Description

There was once a popular game called Infinity Loop. Here is a brief introduction to the game:

The game is played on an $n \times m$ grid board. Some cells contain pipes. A pipe may have joints at the midpoints of the cell’s edges in certain directions. All pipes have the same thickness, so if two adjacent cells both have a joint at the midpoint of their shared edge, those two joints are considered connected. Pipes come in the following $15$ shapes:

At the start of the game, there may be leaks on the board.

Formally: if there exists a joint that is not connected to any other joint, then it is a leak.

The player can perform the following operation: choose a cell containing a non-straight pipe and rotate the pipe by $90$ degrees clockwise or counterclockwise about the center of the cell.

A straight pipe refers to the two shapes in the middle row of the figure on the left.

Given an initial configuration, find the minimum number of operations needed so that there are no leaks on the board.

Input Format

The first line contains two positive integers $n$, $m$, representing the size of the grid.

Each of the next $n$ lines contains $m$ numbers, each in $[0,15]$. You may regard each number as a $4$-bit binary number. From low to high bit, the bits indicate whether in the initial configuration the cell has a joint in the up, right, down, and left directions, respectively.

In particular, if the number is $0$, it means there is no pipe in this cell.

For example, $3(0011_{(2)})$ means there are joints up and right, i.e., an $L$ shape; and $12(1100_{(2)})$ means there are joints down and left, i.e., the $L$ shape rotated by $180$ degrees.

Output Format

Output a single line with the minimum number of operations. If it is impossible to achieve the goal, output $-1$.

2 3
3 14 12
3 11 12

2

3 2
1 8
5 10
2 4

-1

3 3
9 11 3
13 15 7
12 14 6

16

Hint

[Sample 1 explanation]

The board is as follows:

The rotation method is straightforward: first rotate the pipe in the dashed cell at the top-left clockwise by $90$ degrees.

Then rotate the pipe in the dashed cell at the bottom-right counterclockwise by $90$ degrees. This closes the loop.

[Sample 2 explanation]

Sample 2 corresponds to the first picture in the problem description and is impossible to solve.

[Sample 3 explanation]

Sample 3 corresponds to the second picture in the problem description. Rotate the pipe in every cell except the center cell by $180$ degrees.

Translated by ChatGPT 5