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

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

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

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. }

复制代码

这个问题很有意思，先说下我的思路吧，代码有空再写
我觉得，关键是以程序的方法去实现，也就是让程序自动判断，而不是你人为判断好了过河流程，让然再让程序实现你人为的流程，你说对吗？
那么，就开始考虑面对对象思维吧，
1.对象：猫、狗、鱼、船、两岸、人
2.对象的具体属性和方法：
猫：属性，在哪个岸上，傍边是否有人，
       方法：吃鱼
狗：属性：在哪个岸上，傍边是否有人，
      方法：咬猫
鱼：属性：在哪个岸上，傍边是否有人，
     它与世无争，没有什么动作
岸：属性：有哪些个物种
      方法：判断这些物种是否冲突
人：属性：在哪个岸上
船：属性：在哪个岸上
       方法：运输

主程序，判断对岸是否同时具有猫狗鱼和人，如果不是，一直运行船的运输方法

好的，谢谢！！

我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。

1. package com.itheima;
   
2. 
   
3. import java.util.ArrayList;
   
4. import java.util.List;
   
5. 
   
6. /**
   
7. *
   
8. * @author 呆呆沙师妹
   
9. * 题目：
   
10. * 10、 一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。
    
11. * 当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，
    
12. * 则不会发生这种问题。编程解决猫狗鱼过河问题。
    
13. *
    
14. * 思路：
    
15. * 1、建立两个字符串集合ArrayList来存储河岸两边的动物们，
    
16. *    初始时，动物全在河左岸，最终目的是要将河左岸的动物全部运到河右岸；
    
17. * 2、定义函数检查当河岸边动物在无老农情况下是否产生动物损失情况；
    
18. * 3、定义使用船的次数，
    
19. *    当船使用次数为单数时老农在河右岸，只要老农带走的动物后剩下的动物不产生损失，
    
20. *    即将带走的动物添加去河右岸集合中；
    
21. *    船使用次数为偶数时老农在河左岸；如果河右岸动物们不会产生损失，
    
22. *    则老农不带动物回到左岸，否则带走动物保证河右岸动物的安全，将带走动物放回左岸。
    
23. * 4、如果河左岸动物为空，则循环结束。
    
24. *
    
25. */
    
26. public class Test10 {
    
27. 
    
28.         public static void main(String[] args) {
    
29.                 List<String> left = new ArrayList<String>();
    
30.                 List<String> right = new ArrayList<String>();
    
31.                 left.add( "猫" );
    
32.                 left.add( "狗" );
    
33.                 left.add( "鱼" );
    
34.                
    
35.                 int useBoat = 0;
    
36.                 String animal = null;
    
37.                
    
38.                 while( !left.isEmpty() ){
    
39.                     useBoat++;
    
40.                         animal = null;
    
41.                         if( 1 == useBoat % 2 ){
    
42.                                 for( int i = 0; i < left.size(); i++ ){
    
43.                                         animal = left.remove( i );
    
44.                                         if( lossAnimal(left) ){
    
45.                                                 left.add( animal );
    
46.                                                 continue;
    
47.                                         }else{
    
48.                                                 break;
    
49.                                         }
    
50.                                 }
    
51.                                 System.out.println( "第" + useBoat + "次, 老农用船将" + animal + "运到河右岸" );
    
52.                                 right.add( animal );
    
53.                         }else {                       
    
54.                                 while( lossAnimal(right) ){
    
55.                                         for( int i = 0; i < right.size(); i++ ){
    
56.                                                  animal = right.remove( i );
    
57.                                                  if( lossAnimal(right) ){
    
58.                                                          right.add( animal );
    
59.                                                          continue;
    
60.                                                  }else{
    
61.                                                          break;
    
62.                                                  }
    
63.                                    }
    
64.                                 }
    
65.                            if( animal == null ){
    
66.                                    System.out.println( "第" + useBoat + "次, 老农用船回到河左岸" );
    
67.                            }else{
    
68.                                System.out.println( "第" + useBoat + "次, 老农用船将" + animal + "运回河左岸" );
    
69.                                left.add( animal );
    
70.                            }
    
71.                         }
    
72.                 }
    
73.         }
    
74.        
    
75.         public static boolean lossAnimal( List<String> list ){
    
76.                 if( list.contains("猫") && list.contains("狗") ){
    
77.                         return true;
    
78.                 }else if( list.contains("猫") && list.contains("鱼") ){
    
79.                         return true;
    
80.                 }else{
    
81.                         return false;
    
82.                 }                       
    
83.         }
    
84. }
    

复制代码

从思路到代码，想了很久，没办法，智商有点捉急，附件里是程序代码

说一下主要思路吧，第一想法就是，程序自动判断
这个还算简单，但后来我为了扩展性重构了一下代码，那调debug调的我眼睛都花了

恩，回归正题
1.第一种思路你也知道，就是判读如果猫狗，或者鱼猫在一起，那就是不和谐状态，然后就来回倒腾，这个就不多说了
2.但你说想要扩展一下，什么叫扩展？扩展就是在不改变原有程序代码的情况下增加新的功能。
那我是这样处理的，将这些动物都实现一个接口，这个接口中定义了一个自身是否能处于和谐的状态（无论是骚扰或是被骚扰，都是一种不和谐状态）。
这样的话，以后即使增加了一个新的物种，也只需额外判断它自己是否和谐就可以了，不会对原代码产生影响。

好了，这个是核心思想，具体请看附件

另外，本人从没这么认真回答过问题，希望楼主能认真看下，然后给点建议

sanguodouble1 发表于 2014-4-20 18:16
从思路到代码，想了很久，没办法，智商有点捉急，附件里是程序代码

说一下主要思路吧，第一想法就是，程序 ...

挺好的，我当时做的时候本来想让他自己生成的，后来没解决，，我运行了一下你的程序，其实还有另一种过河方法，就是  先带猫过去，农夫返回带鱼过去，然后将猫带回，之后将狗带过去，最后返回将猫带过去，最好这两种都能自动生成吧！

霍振鹏 发表于 2014-4-20 22:50
挺好的，我当时做的时候本来想让他自己生成的，后来没解决，，我运行了一下你的程序，其实还有另一种过河 ...

这个其实能实现的，你只要把猫狗鱼放入集合的顺换一下就可以看到你说的这种现象了，代码实现的话就更简单了，用Collections.shuffle()这个方法打乱一下顺序就可以了。

我认为，主要是不足在这个地方：
比如说有好多物种，跟楼主说的一样判断条件很复杂，这时就会出现这种现象：先把A物种弄到对岸，相安无事，然后把B物种弄到对岸，还是相安无事，
但这个，第三趟把C物种弄到对岸后，发现程序无解了，这时候就需要返回到原来的初始状态重新开始，
也就是说，你每一步都需要记录一个状态，当发现下一步无法进行时，就需要恢复这个状态，当这个状态下所有情况都无法满足条件时，你需要恢复再之前的状态。
你跟走象棋悔棋一样，有时候你需要悔好几步才能达到理想状态（突然想起了国际象棋电脑深蓝）

但请原谅以我的智商，无法将这个思想转换成代码

sanguodouble1 发表于 2014-4-21 13:55
这个其实能实现的，你只要把猫狗鱼放入集合的顺换一下就可以看到你说的这种现象了，代码实现的话就更简单 ...

学习了，非常感谢你的分享。

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

目测中，呆呆师妹的方法效率最高

我想知道，这道题不做的话，其他9道题全做，多少分

我是来学习的！{:3_53:}

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

思路是纯面向对象的方法，我试了试，写不出来，求请教

嗯嗒 正在写这道题

学习学习，谢谢楼主分享...

感觉逻辑好复杂的赶脚

正在写这个……

好的，学习了:lol

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

有BUG 你这个一开始把三种动物放入的顺序随便颠倒一下就是死循环

做到这道题了，一看有点发蒙，过年几天有事，也没细想，看了帖子贴出的程序，与自己的想法有相同也有不同，收获很多。

package com.itheima;

import java.util.ArrayList;

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

public class Test10 {

        public static void main(String[] args) {
                //存放河岸A（起始位置）现有动物
                ArrayList thisLan = new ArrayList<String>();
                //存放河岸B（起始位置）现有动物
                ArrayList thatLan = new ArrayList<String>();
                //添加动物狗
                thisLan.add("猫");
                //添加动物猫
                thisLan.add("鱼");
                //添加动物鱼
                thisLan.add("狗");
                //老农类，实现所以功能
                Fammer fammer = new Fammer();
                //老农类中的dispose方法，其中调用tothatLan与tothisLan方法
                fammer.dispose(thisLan, thatLan);
        }

        //实现农夫运送动物的功能
       
       
}
class Fammer{
        //元素缓存，辅助tothatLan和tothisLan进行元素删除与恢复
        private String temp;
       
        //步骤记录
        private int time = 1;
        //当老农不在时，判断猫狗鱼三者的关系。如果出现狗会咬猫，猫会吃鱼的情况返回false，否则返回true
        public boolean safe(ArrayList<String> a){
                if((a.contains("狗")&&a.contains("猫")) || (a.contains("猫")&&a.contains("鱼"))){
                        return false;
                }
                return true;
        }
        //从河岸A向河岸B运送动物的方法
        public void tothatLan(ArrayList<String> tis,ArrayList<String> tat){
                //用于while循环
                boolean flag = true;
                while(true){
                        //当河岸A没有动物时说明动物均被带到河岸B
                        if(tis.size()==0){
                                //提示结束
                                System.out.println("结束！");
                                return;
                        }
                        //自动查询符合条件的动物，并带到河岸B
                        for (int i = 0; i < tis.size(); i++) {
                                //缓存，用于删除与恢复动物
                                temp = tis.get(i);
                                if(tis.remove(temp)){                                               
                                        if(this.safe(tis)){
                                                System.out.println("第"+time+"步,将"+temp+"从河岸A运送到河岸B");
                                                time++;
                                                //动物过河
                                                tat.add(temp);
                                                temp = null;
                                                System.out.println("            "+"河岸A有"+tis);
                                                System.out.println("            "+"河岸B有"+tat);
                                                return;
                                        }else{
                                                //恢复删除
                                                tis.add(temp);
                                                continue;
                                        }
                                }else{
                                        continue;
                                }
                        }
                }
        }
        //从河岸B向河岸A运送动物的方法,与tothatLan相似
        public void tothisLan(ArrayList<String> tis,ArrayList<String> tat){
                //用于while循环
                boolean flag = true;
                while(flag){
                        //当河岸B的动物符合要求或没有动物，便不需要将动物带回河岸A
                        if(tat.size()<1 || this.safe(tat)){
                                return;
                        }
                        //自动查询符合条件的动物，并带到河岸A
                        for (int i = 0; i < tat.size(); i++) {
                                //缓存，用于删除与恢复动物
                                temp = tat.get(i);
                                if(tat.remove(temp)){
                                        if(this.safe(tat)){
                                                System.out.println("第"+time+"步,将"+temp+"从河岸B运送到河岸A");
                                                time++;
                                                //动物过河
                                                tis.add(temp);
                                                temp = null;
                                                System.out.println("            "+"河岸A有"+tis);
                                                System.out.println("            "+"河岸B有"+tat);
                                                return;
                                        }else{
                                                //恢复删除
                                                tat.add(temp);
                                                continue;
                                        }
                                }else{
                                        continue;
                                }
                        }
                }
        }
        //自动完成动物过河，调用tothatLan和tothisLan的方法
        public void dispose(ArrayList<String> tis,ArrayList<String> tat){
                boolean flag = true;
                while(flag){
                        //当河岸A没有动物说明动物全部过河
                        if(tis.isEmpty()){
                                return;
                        }
                        this.tothatLan(tis, tat);
                        //当河岸A没有动物说明动物全部过河
                        if(tis.isEmpty()){
                                return;
                        }
                        this.tothisLan(tis, tat);
                }
        }
       
}