Notice: You need to enable the flag -std=c++11 to compile the code!
Once upon a time a farmer went to a market and purchased X wolfs, Y goats, and Z cabbages.
On his way home, the farmer came to the left river bank and rented a boat. To cross the river by a boat, the farmer could carry only himself and at most one of his purchases: a wolf, a goat, or a cabbage.
At both left and right banks, if the farmer is not there and the wolves are more than the goats (#W>#G), the wolves will eat the goats. Also, if the farmer is not there and the goats are more than the cabbages (#G>#C), the goats will eat the cabbages.
In this problem, you have to find all solutions that the farmer can carry himself and all his purchases from the left to the right bank.
For each solution, you cannot produce duplicate states.
For example:
This solution isn't allowed because there are duplicate states.
Hint: You can use set<State> _explored to store each state.
The input has only single line containing three integer X Y Z, representing the number of purchased wolves, goats and cabbages.
List all solutions one by one.
"Done" denotes the end of a solution.
A solution contains several moves. Each move is represented by a line with the format of:
(#W at the left, #G at the left, #C at the left)(#W at the right, #G at the right, #C at the right) [left/right]
W: wolf, G: goat, C: cabbage, left/right: position of the boat.
For example:
We've created the function to print outputs from the variable set, so you just need to add your solutions to the variable set<list<State>> _solutions. You don't have to worry about the order of your solutions.