M missionaries and C cannibals want to cross a river using a rowboat that can carry at most R people at a time. Everybody starts out on one side of the river, and they all want to end with everybody on the other side of the river. Although the cannibals and missionaries are friends and are trying to cooperate, if the cannibals ever outnumber the missionaries on either side of the river, or in the rowboat, they will succumb to temptation and eat the poor souls. Given M, C, and R, you
are to return the smallest number of river crossings needed to get everyone safely to the other side of the river. If it is impossible
to get everyone safely across the river, return -1.
Each trip from one side of the river to the other counts as one crossing, so a round trip would count as two river crossings. Also, each crossing requires at least one person in the boat to row. Finally, note that, whenever the boat reaches shore, everybody in the boat temporarily disembarks for the purposes of determining whether the cannibals outnumber the missionaries on that side of the river.
As an example, consider the classic version of this puzzle, where you start with 3 missionaries, 3 cannibals, and a rowboat that can hold up to 2 people. For the first crossing, you must send at least two people, because if you sent only one person, that person would have to immediately bring the rowboat back. If you send two missionaries, the remaining missionary gets eaten by the cannibals. You could safely send two cannibals and have one bring the boat back. Alternatively, you could send one missionary and one cannibal, and then have the missionary bring the boat back (because if the cannibal brought the boat back, the two missionaries on the original side of the river would be eaten). Either way, after two crossings, you have one cannibal on the opposite side of the river.
|