过河问题 - 黑马程序员技术交流社区

import java.util.ArrayList;
/*
* 有一条河，一支船，岸上有一对父母，两个儿子，两个女儿，一个主人一只狗，都要过河，可船只能坐两个人，狗也算。
* 父亲母亲主人会划船，如果父亲走了，母亲会打儿子，母亲走了，父亲会打女儿，主人走了，狗咬人。问8个人怎样平安过河？
*/
public class CopyOfRiverCross {
public static void main(String[] args) {
ArrayList<String> river = new ArrayList<String>();// 河这边
ArrayList<String> cross = new ArrayList<String>();// 对岸
ArrayList<String> boat = new ArrayList<String>();// 船只
river.add("父亲");
river.add("狗");
river.add("主人");
river.add("儿子");
river.add("女儿");
river.add("女儿2");
river.add("儿子2");
river.add("母亲");
while (true) {
group(river, boat,cross);
System.out.print(boat+"坐船过去------");
land(cross, boat);
if (river.isEmpty()) {
System.out.println("--------------------都过去了");
break;
}
getBack(cross, boat,river);
System.out.print(boat+"坐船回来-----");
land(river, boat);
System.out.println(river+"还没过去");
}
}
// 上岸
public static void land(ArrayList<String> land, ArrayList<String> boat) {
land.addAll(boat);
boat.clear();
}
// 返回
public static void getBack(ArrayList<String> cross, ArrayList<String> boat,ArrayList<String> river) {
ArrayList<String> temp = new ArrayList<String>();
ArrayList<String> temp2 = new ArrayList<String>();
boolean b = true;
for (int i = 0; i < cross.size(); i++) {
boat.add(cross.get(i));
temp.addAll(cross);
temp.removeAll(boat);
temp2.addAll(boat);
temp2.addAll(river);
if (isSafe(temp)&isSafe(temp2) & isSail(boat)) {
if (isSafe(temp)) {
cross.removeAll(boat);
b = false;
break;
} else {
boat.clear();
temp.clear();
}
} else {
boat.clear();
temp2.clear();
}
}
if(b){
group(cross,boat,river);
}
}
// 遍历上船的所有组合方式，找出可以开船的方案并上船
public static void group(ArrayList<String> river, ArrayList<String> boat,ArrayList<String> cross) {
ArrayList<String> temp = new ArrayList<String>();
ArrayList<String> temp2 = new ArrayList<String>();
for (int i = 0; i < river.size(); i++) {
for (int n = 0; n < i; n++) {
boat.add(river.get(n));
boat.add(river.get(i));
temp.addAll(boat);
temp.addAll(cross);
temp2.addAll(river);
temp2.removeAll(boat);
if (isSafe(temp)&isSafe(temp2) & isSail(boat)) {
river.removeAll(boat);
break;
} else {
boat.clear();
temp.clear();
}
}
if (isSafe(boat) & isSail(boat)) {
break;
} else {
boat.clear();
}
}
}
// 判断是否安全
public static boolean isSafe(ArrayList<String> list) {
if (!list.contains("父亲")&list.contains("母亲") & (list.contains("儿子")|list.contains("儿子2"))||
!list.contains("母亲")&list.contains("父亲") & (list.contains("女儿")|list.contains("女儿2"))||
!list.contains("主人") & list.contains("狗")&(list.contains("父亲")|list.contains("母亲")|
list.contains("儿子")|list.contains("儿子2")|list.contains("女儿"))) {
return false;
}
return true;
}
// 判断是否能开船
public static boolean isSail(ArrayList<String> list) {
if (list.contains("父亲") || list.contains("母亲") || list.contains("主人")) {
return true;
}
return false;
}
}

复制代码