PROGRAMMING:Man wolf sheep vegetable crossing the river
A man should transport a wolf, a sheep and a basket of vegetables to the other side of the river. But his boat is too small to carry one at a time. When he is away, the wolf will eat the sheep and the sheep will eat the vegetables. How can they be safely transported across the river?
Please write a program to find out all the plans for crossing the river.
Four letters are used to indicate the state of man, wolf, sheep and vegetable
-M is used to indicate the presence of a person and. Is used to indicate the absence of a person
-W means the wolf is in, w means the wolf is not
-G means the sheep are in, and. Means the sheep are not
-C means the dish is here, and C means the dish is not here
-It is indicated that the ship goes from left bank to right bank by using >, and it is indicated that the ship goes from right bank to left bank by using <.
For example:
If all the dishes are on the left bank, the status is
```
MWGC -> ....
```
If a man transports the sheep to the right bank and there are only wolves and vegetables left on the left bank, then the state is expressed as
```
.W.C <- M.G.
```
####Input format
>Initial state
>Termination status
####Output format
>If there are solutions, all solutions are output.
>Each solution consists of several lines, and each line represents a state.
>There is a blank line between different solutions.
>If there is no solution, output none.
####Input sample 1
```in
MWGC -> ....
.... <- MWGC
```
####Output sample 1
```out
MWGC -> ....
.W.C <- M.G.
MW.C -> ..G.
...C <- MWG.
M.GC -> .W..
..G. <- MW.C
M.G. -> .W.C
.... <- MWGC
MWGC -> ....
.W.C <- M.G.
MW.C -> ..G.
.W.. <- M.GC
MWG. -> ...C
..G. <- MW.C
M.G. -> .W.C
.... <- MWGC
```
####Input sample 2
```in
.W.. <- M.GC
M.GC -> .W..
```
####Output sample 2
```out
.W.. <- M.GC
MWG. -> ...C
..G. <- MW.C
M.GC -> .W..
.W.. <- M.GC
MW.C -> ..G.
...C <- MWG.
M.GC -> .W..
```
---
The topic ensures that the input initial state and termination state are different, and the situation of wolf eating sheep and sheep eating vegetables will not occur, and the ship and people are together.
In order to make the output solutions in the same order, people are required to try in the following order every time they cross the river
-Crossing the river without anything
-Take the wolf across the river
-Take sheep across the river
-Crossing the river with vegetables
And the output of each solution is not allowed to appear in two lines of the same state.
answer：If there is no answer, please comment
| ![ Title. JPG] (~ / ea91c620-4fc5-4da3-8602-2dea157edfbe. JPG) |
Please write a program to find out all the plans for crossing the river.
Four letters are used to indicate the state of man, wolf, sheep and vegetable
-M is used to indicate the presence of a person and. Is used to indicate the absence of a person
-W means the wolf is in, w means the wolf is not
-G means the sheep are in, and. Means the sheep are not
-C means the dish is here, and C means the dish is not here
-It is indicated that the ship goes from left bank to right bank by using >, and it is indicated that the ship goes from right bank to left bank by using <.
For example:
If all the dishes are on the left bank, the status is
```
MWGC -> ....
```
If a man transports the sheep to the right bank and there are only wolves and vegetables left on the left bank, then the state is expressed as
```
.W.C <- M.G.
```
####Input format
>Initial state
>Termination status
####Output format
>If there are solutions, all solutions are output.
>Each solution consists of several lines, and each line represents a state.
>There is a blank line between different solutions.
>If there is no solution, output none.
####Input sample 1
```in
MWGC -> ....
.... <- MWGC
```
####Output sample 1
```out
MWGC -> ....
.W.C <- M.G.
MW.C -> ..G.
...C <- MWG.
M.GC -> .W..
..G. <- MW.C
M.G. -> .W.C
.... <- MWGC
MWGC -> ....
.W.C <- M.G.
MW.C -> ..G.
.W.. <- M.GC
MWG. -> ...C
..G. <- MW.C
M.G. -> .W.C
.... <- MWGC
```
####Input sample 2
```in
.W.. <- M.GC
M.GC -> .W..
```
####Output sample 2
```out
.W.. <- M.GC
MWG. -> ...C
..G. <- MW.C
M.GC -> .W..
.W.. <- M.GC
MW.C -> ..G.
...C <- MWG.
M.GC -> .W..
```
---
The topic ensures that the input initial state and termination state are different, and the situation of wolf eating sheep and sheep eating vegetables will not occur, and the ship and people are together.
In order to make the output solutions in the same order, people are required to try in the following order every time they cross the river
-Crossing the river without anything
-Take the wolf across the river
-Take sheep across the river
-Crossing the river with vegetables
And the output of each solution is not allowed to appear in two lines of the same state.
answer：If there is no answer, please comment