1. import java.util.ArrayList;
   
2. /*
   
3. * 有一条河，一支船，岸上有一对父母，两个儿子，两个女儿，一个主人一只狗，都要过河，可船只能坐两个人，狗也算。
   
4. * 父亲母亲主人会划船，如果父亲走了，母亲会打儿子，母亲走了，父亲会打女儿，主人走了，狗咬人。   问8个人怎样平安过河？
   
5. */
   
6. public class CopyOfRiverCross {
   
7.         public static void main(String[] args) {
   
8.                 ArrayList<String> river = new ArrayList<String>();// 河这边
   
9.                 ArrayList<String> cross = new ArrayList<String>();// 对岸
   
10.                 ArrayList<String> boat = new ArrayList<String>();// 船只
    
11.                 river.add("父亲");
    
12.                 river.add("狗");
    
13.                 river.add("主人");
    
14.                 river.add("儿子");
    
15.                 river.add("女儿");
    
16.                 river.add("女儿2");
    
17.                 river.add("儿子2");
    
18.                 river.add("母亲");
    
19.                 while (true) {
    
20.                         group(river, boat,cross);
    
21.                         System.out.print(boat+"坐船过去------");
    
22.                         land(cross, boat);
    
23.                         if (river.isEmpty()) {
    
24.                                 System.out.println("--------------------都过去了");
    
25.                                 break;
    
26.                         }
    
27.                         getBack(cross, boat,river);
    
28.                         System.out.print(boat+"坐船回来-----");
    
29.                         land(river, boat);
    
30.                         System.out.println(river+"还没过去");
    
31.                 }
    
32.         }
    
33. 
    
34.         // 上岸
    
35.         public static void land(ArrayList<String> land, ArrayList<String> boat) {
    
36.                 land.addAll(boat);
    
37.                 boat.clear();
    
38.         }
    
39. 
    
40.         // 返回
    
41.         public static void getBack(ArrayList<String> cross, ArrayList<String> boat,ArrayList<String> river) {
    
42.                 ArrayList<String> temp = new ArrayList<String>();
    
43.                 ArrayList<String> temp2 = new ArrayList<String>();
    
44.                 boolean b = true;
    
45.                 for (int i = 0; i < cross.size(); i++) {
    
46.                         boat.add(cross.get(i));
    
47.                         temp.addAll(cross);
    
48.                         temp.removeAll(boat);
    
49.                         temp2.addAll(boat);
    
50.                         temp2.addAll(river);
    
51.                         if (isSafe(temp)&isSafe(temp2) & isSail(boat)) {
    
52.                                 if (isSafe(temp)) {
    
53.                                         cross.removeAll(boat);
    
54.                                         b = false;
    
55.                                         break;
    
56.                                 } else {
    
57.                                         boat.clear();
    
58.                                         temp.clear();
    
59.                                 }
    
60.                         } else {
    
61.                                 boat.clear();
    
62.                                 temp2.clear();
    
63.                         }
    
64.                 }
    
65.                 if(b){
    
66.                         group(cross,boat,river);
    
67.                 }
    
68.         }
    
69. 
    
70.         // 遍历上船的所有组合方式，找出可以开船的方案并上船
    
71.         public static void group(ArrayList<String> river, ArrayList<String> boat,ArrayList<String> cross) {
    
72.                 ArrayList<String> temp = new ArrayList<String>();
    
73.                 ArrayList<String> temp2 = new ArrayList<String>();
    
74.                 for (int i = 0; i < river.size(); i++) {
    
75.                         for (int n = 0; n < i; n++) {
    
76.                                 boat.add(river.get(n));
    
77.                                 boat.add(river.get(i));
    
78.                                 temp.addAll(boat);
    
79.                                 temp.addAll(cross);
    
80.                                 temp2.addAll(river);
    
81.                                 temp2.removeAll(boat);
    
82.                                 if (isSafe(temp)&isSafe(temp2) & isSail(boat)) {
    
83.                                         river.removeAll(boat);
    
84.                                         break;
    
85.                                 } else {
    
86.                                         boat.clear();
    
87.                                         temp.clear();
    
88.                                 }
    
89.                         }
    
90.                         if (isSafe(boat) & isSail(boat)) {
    
91.                                 break;
    
92.                         } else {
    
93.                                 boat.clear();
    
94.                         }
    
95.                 }
    
96.         }
    
97. 
    
98.         // 判断是否安全
    
99.         public static boolean isSafe(ArrayList<String> list) {
    
100.                 if (!list.contains("父亲")&list.contains("母亲") & (list.contains("儿子")|list.contains("儿子2"))||
     
101.                         !list.contains("母亲")&list.contains("父亲") & (list.contains("女儿")|list.contains("女儿2"))||
     
102.                         !list.contains("主人") & list.contains("狗")&(list.contains("父亲")|list.contains("母亲")|
     
103.                         list.contains("儿子")|list.contains("儿子2")|list.contains("女儿"))) {
     
104.                         return false;
     
105.                 }
     
106.                 return true;
     
107.         }
     
108. 
     
109.         // 判断是否能开船
     
110.         public static boolean isSail(ArrayList<String> list) {
     
111.                 if (list.contains("父亲") || list.contains("母亲") || list.contains("主人")) {
     
112.                         return true;
     
113.                 }
     
114.                 return false;
     
115.         }
     
116. }

复制代码

把添加元素的顺序打乱，有时候可能会影响到效率，不过还没有验证是否8个元素随机排列无死循环，到时候用Map集合for循环试一下

过河类的都是一个思路，条件的判断和元素的遍历，主要就是这2点，在条件的限制下，尽量是多人过河少人回的原则，这类问题的解决也就是这样，不难

这是哪里的题，好变态的说

帅帅loyal 发表于 2015-8-16 19:28
这是哪里的题，好变态的说

这类问题的核心就是判断和对集合的元素的遍历，for循环或者while循环或者递归，至少最简单的解法是这样，比遍历文件夹简单多了，你仔细看一遍就会解类似这样的过河的题目了，&和|的和集合，包含的知识点比较少的

基础题里面的？

pengbeilin 发表于 2015-8-16 21:15
基础题里面的？

都是些基础，不要看有这么多，其实就逻辑符，集合，遍历这些，视频里面都会详细讲的知识点

之前我的是 人和狗猫鱼过何比较简单

很好，经典问题

这个要学习啊

这个有意思啊

看着好多啊，不过貌似里面的东西不是非常难，还可以理解

pengbeilin 发表于 2015-8-16 22:31
之前我的是 人和狗猫鱼过何比较简单

把判断条件改一改，就是一样的原理了

阮文江 发表于 2015-8-16 23:57
看着好多啊，不过貌似里面的东西不是非常难，还可以理解

这代码写完还没有优化，看着就比较多，比如可以把开头的while循环换成递归，过河和返回可以写出一个方法共用，

脑袋有点乱。

lh5484826 发表于 2015-8-17 12:32
脑袋有点乱。

我代码刚刚写完还没优化就发了
但其实你从下面看回头就懂了，最下面是条件判断，往上分别是过河与返回的方式，最上面就是集合...

代码看得好晕啊！！！

脑子不够用了，好难

学习一下

有意思的题目，谢楼主。