Article From:https://www.cnblogs.com/maomao9173/p/9971283.html

There is one\(n\)That’s ok\(m\)The black-and-white chessboard of the column, you can exchange the chessboard in two adjacent lattices (adjacent refers to having common edges or common vertices) at a time, and finally reach the goal state. Request No.\(i\)Xing di\(j\)The lattice of a column can only participate\(m[i][j]\)Secondary exchange.

### Input Format:

The first line contains two integers\(n，m（1<=n, m<=20）\)

Following\(n\)Behavior Initial State, Each Behavior Includes One\(m\)Character\(01\)String, of which\(0\)Represents a black chess piece.\(1\)Represents a white chess piece.

Following\(n\)Behavior target state in the same format as the initial state.

Following\(n\)A row contains one for each action\(m\)individual\(0-9\)A string of numbers representing the upper limit of the number of times each lattice participates in the exchange.

### Output Format:

The output is only one line, which is the minimum total number of swaps. If there is no solution, output\(-1\)

Input sample #1:

``````3 3
110
000
001
000
110
100
222
222
222``````

Output sample #1:

``4``

#### In order to help you sort out the ideas, here I paste the drawing process:

• Initial point – & gt;\(S\) \(f=1\) \(w=0\)
• Final point & lt;-\(T\) \(f=1\) \(w=0\)
• Initial point – & gt; corresponding coordinates\(mid\)node\(f=1\) \(w=0\)
• Corresponding coordinates\(mid\)Node – & gt; termination point\(f=1\) \(w=0\)
• The eight links in the chessboard: (1)\(out\)->\(in\)) \(f=INF\) \(w=1\)
• \(inn\)->\(mid\)and\(mid\)->\(out\)\(w=1\)，Confirm the choice according to the situation\(f=maxf/2\) perhaps\(f=(maxf+1)/2\)