狗猫鱼过河问题，分享我的代码和思路 - 黑马程序员技术交流社区

import java.util.*;
/**
* 思路：使用递归。在此岸枚举动物过河，判断剩下是否能够共存，如果过河了，判断对岸的是否可以共存，两边轮流枚举，知道对岸的能够共存为此。
* @author 朦胧色彩
*/
public class Test {
private static int go = -1; // 记住过河的动物
private static int back = -1; // 记录回头的动物
private static String animal[] = {"狗", "猫", "鱼"};
public static void main(String[] args) {
ArrayList<Integer> here = new ArrayList<Integer>();
ArrayList<Integer> there = new ArrayList<Integer>();
System.out.println("0代表狗，1代表猫，2代表鱼"+"\n");
// 初始化此岸的动物有哪些
for(int i = 0;i < 3; i++)
here.add(i);
// 一开始是过河
crossRiver(here, there, true, -1);
there.add(here.get(0));
here.remove(0);
System.out.println("最后农夫和猫过河");
System.out.println("此岸："+here+"\t彼岸："+there);
}
/*
* a b 代表此岸，彼岸或者（彼岸，此岸），具体由where决定
* where 代表的是过河和回来 true是此岸去彼岸，false是彼岸回此岸
* type 是记录上一次过河或者回来的是哪种动物
*/
public static void crossRiver(ArrayList<Integer> a, ArrayList<Integer> b, boolean where, int type)
{
if(where) // 过
System.out.println("此岸："+a+"\t彼岸："+b);
else // 回
System.out.println("此岸："+b+"\t彼岸："+a);
for(int i = 0; i < a.size() ; i++)
{
if(type != a.get(i))
{
int temp = a.get(i);
//System.out.println(temp + " " + i);
a.remove(i);
if(!isOk(a) && a.size() > 1){
a.add(temp);
Collections.sort(a);
}
else
{
// 如果是过河的，那么用go记录住这次是谁过的，如果过了对岸，发现不能共存的话，就不能是它回头了，避免死循环
if(where){
go = temp;
System.out.println("农夫和"+animal[temp]+"过河");
}
// 回头的，back记录住谁回头了
else{
back = temp;
System.out.println("农夫和"+animal[temp]+"回河");
}
b.add(temp);
Collections.sort(b);
// 如果对岸只有一种动物，那么此岸还要继续
if(b.size() == 1)
{
//System.out.println(a+" "+b+"-1");
crossRiver(a, b, true, back);
}
// 当该岸已经有两种动物了，那就要判断是否能够共存，这里是不能共存的操作
else if(!isOk(b))
{
//System.out.println(b+" "+a+"-2");
if(where) // 如果是刚过去的，且目前该岸不能共存的话，那就回一种动物到对岸，并且该种动物不能是go
crossRiver(b, a, false, go);
else // 如果是刚回来的，且目前该岸不能共存的话，那就过一种动物到对岸，并且该种动物不能是back
crossRiver(b, a, true, back);
}
else
{
//System.out.println(a+" - " + b + "="+back);
crossRiver(a, b, true, back);
}
}
}
}
}
// 判断农夫所在的岸边是否能够共存
public static boolean isOk(ArrayList<Integer> arr)
{
int sum = 0;
if(arr.size() < 2)
return false;
for(int i = 0; i < arr.size(); i++)
sum += arr.get(i);
// 狗和猫相加是1，猫和鱼相加是3，都是不能共存的
if(sum == 1 || sum == 3)
return false;
return true;
}
}

复制代码