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``

#### So here is the problem of dealing with this boundary. If the chessboard begins and endsIf we have or don’t have the chess pieces, then we have the right to use them.\(maxf\)take\(1/2\)。Otherwise, consider the situation of entering and going out separately: #### 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\)