问题是：一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。编程解决猫狗鱼过河问题。

这是我基础测试时的一道题，我尽力用代码解出来了，但感觉不是非常好。我写的代码只是针对这个题的，如果换几个过河条件我的代码需要全部重写，当过河逻辑再难一点时我的这种解法就很难再有效果了。
希望有人可以指导我一下，写出一个普遍的解法，比如当过河条件变成这样：河边有警察、犯人、爸爸、妈妈、两个小男孩、两个小女孩和一条船，条件是当警察不在时犯人会伤害其他人，当爸爸不在时妈妈会伤害小男孩，当妈妈不在时爸爸会伤害小女孩，警察、爸爸、妈妈会开船，船一次只能拉两个人（算上开船的），请安全的把这些人送到对岸去。
希望有人指导一下，我希望写出一个好的解题方法，可以处理这类过河问题，比如当过河的条件更复杂时可以用程序计算出有没有过河的解，以及过河的具体步骤。

下面是我解农夫过河的代码（感觉很差，请大家指导）：

1. public class Test10 {
   
2.         int farmer,cat,dog,fish; //刚开始都为0，也就是都在河的这岸
   
3.         String type = ""; //记录农夫上一步带的是什么，防止出现死循环,当农夫自己走时type不改变
   
4.         String isnull = "";//当农夫自己走时，isnull会记录下来，防止出现死循环。
   
5.         boolean boo = false;
   
6.         public static void main(String[] args) {
   
7.                 Test10 test = new Test10();
   
8.                 int x = 1;//记录移动的数次
   
9.                 while(true){
   
10.                    test.move();
    
11.            System.out.println("第"+x+"步");
    
12.            System.out.println("河这岸有："+test.print(0));
    
13.            System.out.println("河对岸有："+test.print(1));
    
14.            x++;
    
15.            //当把全部东西都移动到对岸时，即可停止移动。
    
16.            if(test.farmer==1&&test.cat==1&&test.dog==1&&test.fish==1){
    
17.                break;
    
18.            }
    
19.            }
    
20.                     
    
21.             
    
22.         }
    
23.         
    
24.         //农夫过河时需要判断能带什么不能带什么
    
25.         public void move(){
    
26.                
    
27.                 if(farmer==0){
    
28.                         if(cat==0){
    
29.                                 if(!type.equals("cat")){
    
30.                                         farmer = 1;
    
31.                                         cat = 1;
    
32.                                         if(isSafe()){
    
33.                                                 type = "cat";
    
34.                                                 return;
    
35.                                         }else{
    
36.                                                 farmer = 0;
    
37.                                                 cat = 0;
    
38.                                         }
    
39.                                 }
    
40.                         }
    
41.                         if(dog==0){
    
42.                                 if(!type.equals("dog")){
    
43.                                         farmer = 1;
    
44.                                         dog = 1;
    
45.                                         if(isSafe()){
    
46.                                                 type = "dog";
    
47.                                                 return;
    
48.                                         }else{
    
49.                                                 farmer = 0;
    
50.                                                 dog = 0;
    
51.                                         }
    
52.                                 }
    
53.                         }
    
54.                         if(fish==0){
    
55.                                 if(!type.equals("fish")){
    
56.                                         farmer = 1;
    
57.                                         fish = 1;
    
58.                                         if(isSafe()){
    
59.                                                 type = "fish";
    
60.                                                 return;
    
61.                                         }else{
    
62.                                                 farmer = 0;
    
63.                                                 fish = 0;
    
64.                                         }
    
65.                                 }
    
66.                         }
    
67.                                 farmer = 1;
    
68.                         
    
69.                 }else if(farmer==1){
    
70.                         //当人在河对岸时需要优先考虑自已到这岸来，从而把东西带到对岸。
    
71.                         if(isnull != "farmer"){
    
72.                                 farmer = 0;
    
73.                                 isnull = "farmer";
    
74.                                 if(isSafe()){
    
75.                                         return;
    
76.                                 }else{
    
77.                                         farmer = 1;
    
78.                                 }
    
79.                         }
    
80.                                 
    
81.                         if(cat==1){
    
82.                                 if(!type.equals("cat")){
    
83.                                         farmer = 0;
    
84.                                         cat = 0;
    
85.                                         if(isSafe()){
    
86.                                                 type = "cat";
    
87.                                                 isnull = "";
    
88.                                                 return;
    
89.                                         }else{
    
90.                                                 farmer = 1;
    
91.                                                 cat = 1;
    
92.                                         }
    
93.                                 }
    
94.                         }
    
95.                         if(dog==1){
    
96.                                 if(!type.equals("dog")){
    
97.                                         farmer = 0;
    
98.                                         dog = 0;
    
99.                                         if(isSafe()){
    
100.                                                 type = "dog";
     
101.                                                 isnull = "";
     
102.                                                 return;
     
103.                                         }else{
     
104.                                                 farmer = 1;
     
105.                                                 dog = 1;
     
106.                                         }
     
107.                                 }
     
108.                         }
     
109.                         if(fish==1){
     
110.                                 if(!type.equals("fish")){
     
111.                                         farmer = 0;
     
112.                                         dog = 0;
     
113.                                         if(isSafe()){
     
114.                                                 type = "fish";
     
115.                                                 isnull = "";
     
116.                                                 return;
     
117.                                         }else{
     
118.                                                 farmer = 1;
     
119.                                                 fish = 1;
     
120.                                         }
     
121.                                 }
     
122.                         }
     
123.                 }
     
124.         }
     
125.         
     
126.         //判断现在的状态是否有冲突
     
127.         public boolean isSafe(){
     
128.                 if(farmer==1){
     
129.                         if(cat==0&&fish==0)return false;
     
130.                         if(cat==0&&dog==0)return false;
     
131.                 }else if(farmer==0){
     
132.                         if(cat==1&&fish==1)return false;
     
133.                         if(cat==1&&dog==1)return false;
     
134.                 }
     
135.                 return true;
     
136.         }
     
137.         
     
138.         //打印现在河的两岸都有什么
     
139.         public String print(int i){
     
140.                 if(i==0){
     
141.                         String str = "";
     
142.                         if(farmer==0)str += "农夫    ";
     
143.                         if(dog==0)str += "狗    ";
     
144.                         if(cat==0)str += "猫    ";
     
145.                         if(fish==0)str += "鱼    ";
     
146.                         return str;
     
147.                 }else if(i==1){
     
148.                         String str = "";
     
149.                         if(farmer==1)str += "农夫    ";
     
150.                         if(dog==1)str += "狗    ";
     
151.                         if(cat==1)str += "猫    ";
     
152.                         if(fish==1)str += "鱼    ";
     
153.                         return str;
     
154.                 }
     
155.                 return null;
     
156.         }
     
157. 
     
158. }

复制代码

sanguodouble1 发表于 2014-4-20 11:24
这个问题很有意思，先说下我的思路吧，代码有空再写
我觉得，关键是以程序的方法去实现，也就是让程序自动 ...

这样一份感觉思路清晰多了

学习学习

第一步：把猫带过去；
第二步：农夫回来把鱼（狗）带过去；
第三步：农夫回来的时候把猫带回来再把狗（鱼）带过去；
第四步：农夫在回来把猫带过去。

呆呆沙师妹 发表于 2014-4-20 13:51
我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。
...

写的很好，不过有一个地方有Bug，
if( lossAnimal(left) ){
    left.add( animal );
    continue;
}

把动物remove()以后，再添加时，如果不加用添加的位置，就会默认放在后面，这样在遍历时就出现了Bug

楼主成功运行了吗，我怎么在自己的电脑上变异不上呢

呆呆沙师妹 发表于 2014-4-20 13:51
我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。
...

真心点赞,写不出来

都是面向对象的思想,,难道社招的难度大那么多?

看了好几天了

逻辑最简单了，算法怎么才能最好呢

关度飞 发表于 2014-8-11 00:51
嗯嗒 正在写这道题

刚看到你写的时间，话说你现在工作多久了？感觉怎么样呢

很不错，是大神

我也正在写这道题！！

呆呆沙师妹 发表于 2014-4-20 13:51
我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。
...

你的实现不了，只要把集合中鱼的位置排到第一位，你循环几千次都出不来

我是来学习的。。

这题知道怎么过 可是一到代码上就懵圏了

高手啊

另外，这个问题可以谈对象抽取和方法封装的设计，谈类的设计，至于算法的高效，到底用广搜和深搜，还是自动机，动态规划，又是状态之类的，其实没有太大意思。这是个较为特殊的特例问题，而且解决方案也较为单一的问题，不是什么需要大优化之类的问题规模很大的问题。

sanguodouble1 发表于 2014-4-20 11:24
这个问题很有意思，先说下我的思路吧，代码有空再写
我觉得，关键是以程序的方法去实现，也就是让程序自动 ...

    哥们，这个问题，你就不要人为的复杂化了，也不要求一个通用解，如果非要求一个通用解，那么只是适合于A,B，C这种模式，也即狗、猫、鱼。
    这个问题抽象出来后和你举得那个扩展例子抽象出来后不是一个类型的问题，好比x2和x3的方程的解决方法和解决需要的条件不同一样，看似类似，实则不同。
    猫狗鱼问题抽象出来后，是"A->B->C"，这个模式的问题，优先运走，度为2的对象（即B），而且这个有向图中不允许存在两个度为2的对象，也不允许存在度为3的对象，这个度包括出度和入度。否则，就是无解。
所以，这个问题主要是用来锻炼大家的对象抽取能力和设计能力，以及问题的分析能里。
      
     这个不是一个可以扩展的问题，要扩展也只能扩展成（A->B->C   D->E->F），你的扩展就属于另一个问题，不属于和原问题同类型的问题了。用到的东西可能会更多，问题难度要大很多。3个的可能只是一个特例。这个就好比2重积分可以看成是3重积分的一个特例一样，但是3重积分的解法是更复杂的问题。
     最后，真想扩展，那你也要先固定好到底是几个对象，几个约束条件，几个可以渡河运送人的等等，不固定，就谈不上问题的通解，尤其使用程序来做这件事，也许数学还可以有通解。

这题我头疼