2.1 across the river intelligence game
(1) project description
The rules of the game: a six (father, mother, two daughters, two sons) and the police and the thief from the river side
Crossing to the other side of the river, only a small boat on the river side can take them to the other side, but only the father, mother and p
Was able to sail a boat, no matter adults and children, each process can only carry two people, in the process of crossing the river, you should avoid the following three types of mood
Conditions occur:
(1) when the police separated from the thief, the thief can damage a 6 mouth;
(2) when the father saw the mother left, my father will teach daughter;
(3) when mommy sees daddy left, my mother will teach son,
The game see guohe. SWF,
Students are required to give a set of cross feasible solution
(2) solution
[] data structure modeling
A total of eight people, everyone has two states (left and right bank), we have eight people in the state of the left bank of
,0,0,0,0,0,0,0 [0], in the right bank notes for,1,1,1,1,1,1,1 [1], so, this project is to find a from
,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0 [0] to [1],
This state we can actually create a eight elements of an array, you also need to set a variable represents the ship's
State, because print result, therefore in the process of search will also need a storage structure array every time people cross the river
Who is (may be one person, also may be two people), of course, can also set up two instead of one dimensional array structure arrays,
You can choose the depth first search or search breadth first search, each state constraints root
According to the question can be concluded that
A final array of traverse storage crossing the river, and print out the results,
In fact everyone's state (including the state of the ship is 0 or 1), so it is ok to actually use an int type,
State transition all use bit operations,
[model]
Use 2 the integer times of power according to different people, so using an integer in the current situation, 255 as the initial, 0
To end,
{POLICE=0 x80, THIEF=0 x40, DAD=0 x20, BOY1=0 x10, BOY2=0 by 8, MOM=0 x4, GIRL1=0 x
2, GIRL2=0 x1, ALL=0 XFF, OK=0};
(3) the problem extension
Array storage condition, transformation for using a byte to indicate status of each person, and then using an operation mode to
Upgrade,