We can use four-dimensional vectors to represent the state, in which the first component represents people, the second component represents wolves, and the third component represents scales.

Show sheep, and the fourth component represents vegetables; When people or things are on this shore, the corresponding component is 1, and it is 0 when they are on the other shore.

According to the meaning of the question, when people are not present, wolves should eat sheep and sheep should eat vegetables. Therefore, when people are not present, wolves cannot be compared with sheep.

Plant vegetables on both sides of the river. For example, the state (0, 1, 1, 0) means that people and vegetables are there, and wolves and sheep are here.

At this time, wolves will eat sheep without anyone present, so this state is not feasible.

We have listed all the feasible states by exhaustive method, and the feasible states are as follows.

( 1, 1, 1, 1),( 1, 1, 1,0),( 1, 1,0, 1),( 1,0, 1, 1),( 1,0, 1,0)

(0, 1,0, 1),(0, 1,0,0),(0,0, 1,0),(0,0,0, 1),(0,0,0,0)

There are ten possible states. Every time I cross the river, I change the existing state. Now construct a weighted graph G = (V, e, w),

Where the vertices in the set V represent ten feasible states if and only if there is one feasible state between the corresponding two feasible states.

Only when two vertices are connected by a line and the corresponding weight is 1, when there is no feasible transition between the two vertices,

The corresponding weight can be ∞.

Therefore, the problem becomes to find a line in graph G, which starts from the initial state (1, 1, 1, 1) and arrives through the minimum number of transitions.

The transition process of the final state (0,0,0,0), that is, from the state (1, 1, 1, 1) to the state (0,0,0).

The shortest path. This turns the problem into the shortest path problem in graph theory.

Next, the adjacency matrix is calculated first. Because the existing state will be changed after a ferry, four-dimensional state transition is introduced.

The moving vector is used to reflect the situation of the ferry. 1 means crossing the river, and 0 means not crossing the river. For example, (1, 1, 0) means

People take dogs across the river. There are only four cases of state transition, which are represented by the following vector.

( 1,0,0,0),( 1, 1,0,0),( 1,0, 1,0),( 1,0,0, 1)

Now, the operation between the state vector and the transition vector is specified as follows

0 + 0 = 1, 1+ 0 = 1 , 0 + 1 = 1 , 1+ 1 = 1

Through the above definition, if the new vector obtained by adding a feasible state to the transition vector still belongs to a feasible state, then these two

There is an edge between the vertices corresponding to each feasible state. When programming with a computer, we can use ordinary vector operations.

Realization of modulo 2 operation.

Contact me with the source program and I will send it to you.