三个人、一只大猴子、两只小猴子要过河，只有一艘小船，只能载两个单位(两人、两猴或一人一猴)。只有人与那只大猴子能划船，任何时刻，任何地方(岸上、船上、船靠岸时船与岸上合计)，猴子的数量不能多于人的数量，否则会有坏事发生(人家出题要用人与猴没办法，还让猴来欺负人，下次给别人出题选个其他的，什么老虎、大象之类的。不会受歧视，还有气魄)。这帮家伙如何过河才会使三个人都是安全的。
老题了，好久没写这种程序了，有点手痒，回去写了个程序搞定。
渡河过程中，把船在岸时，在一边岸上猴、人、船组成的一个向量作为一个状态，每一种有效状态作为图的一个点。有效状态就是不会有坏事发生的状态，因为程序中只取一边岸上的情况作为状态点，所以这个不会有坏事发生的概念是指两边岸上都是正常而言(不要这边有2人0(或1)猴，看起来是个有效状态，但另一边还有一个倒霉蛋)。同时考虑到小猴不会划船，所以把那种(0大，I小，0人，有船)、(1大，I人，满人，无船)这种状态也排除了，上述的点虽然也可以算是有效点，但上述的点在图中肯定是孤立的，因为在渡河过程中肯定是不会产生上述的情况的。
把点构造好了，那图中的点的链接情况呢？实际上就是在两状态之间能否互相转化的问题了，这里程序中用了比较野蛮的手段。直接把两个表示状态的struct相减，看相减的结果有无符合要求。
MStatus SubValue = M1 - M2;
string TransStr = SubValue.ToString();
switch (TransStr) {
case "0,1,1,1":
case "1,1,0,1":
case "1,0,1,1":
case "1,0,0,1":
case "0,0,1,1":
case "0,0,2,1":
case "0,-1,-1,-1":
case "-1,-1,0,-1":
case "-1,0,-1,-1":
case "-1,0,0,-1":
case "0,0,-1,-1":
case "0,0,-2,-1":
return true;
default:
return false;
}
MStatus就是定义的表示状态的struct。它们相减得到的结果表示为字符串形式如："0,1,1,1"就表示M1比M2多了0只大猴、一只小猴，一个人，一条船，显然M1与M2之间是可以通过一次渡河来相互转化的，在两者之间就可以连一条线。除了上面的12种情况，M1与M2之间无法通过一次渡河解决的就是无法相互转化的。上面也就只有12种情况，而且这12种情况都容易构造，所以用比较难看的方法解决了。
现在的问题转化为，要找一条从初始状态为(0大、0小、0人、无船)的点，到终止状态为(1大、2小、3人、有船)的点的一条路径。呵呵，这就简单了，图论，一次深度优先搜索搞定。
最后的结果：
1、0,0,0,0
2、1,1,0,1
3、0,1,0,0
4、1,2,0,1
5、0,2,0,0
6、0,2,2,1
7、0,1,1,0
8、1,1,2,1
9、1,0,1,0
10、1,0,3,1
11、0,0,3,0
12、1,1,3,1
13、0,1,3,0
14、1,2,3,1