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

import java.util.*;
/**
* 10、一位老农带着猫、狗、鱼过河，河边有一条船，
每次老农只能带一只动物过河。
当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，
当老农和猫狗鱼在一起时，则不会发生这种问题。
编程解决猫狗鱼过河问题。
* */
public class Test10 {
//内部类，存放步骤
private class Node {
int[] arr;
String mesg;
public void set(int[] arr, String mesg) {
this.arr = arr;
this.mesg = mesg;
}
public String toString() {
return Arrays.toString(arr) + "::" + mesg;
}
}
//将步骤入队列
private void set(int[] arr,String mesg){
Node node=new Node();
int[] arrs=Arrays.copyOf(arr, arr.length);
node.set(arrs, mesg);
list.add(node);
}
//判断步骤是否安全
//及判定当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，
private boolean isSafe(int arr[]){
if(arr[0]==0&&arr[1]==1&&(arr[2]==1||arr[3]==1))
return false;
return true;
}
//判定是否安全，每一步是否与队列中步骤有重复。
private boolean isVaid(int[] arr){
for (Iterator<Node> iterator = list.iterator(); iterator.hasNext();) {
Node node = iterator.next();
int [] arrs=node.arr;
if(Arrays.equals(arr, arrs)){
return false;
}
}
return true;
}
//设置循环终点
//当arr最中结果，全0
private boolean isEnd(int [] arr){
int [] arrs=new int[arr.length];//int类型数组初始化为全0
//判断结果arr与arrs是否相等
if(Arrays.equals(arrs, arr)){
//如果相等表示循环条件不满足返回false
return false;
}
//如果不相等表示循环条件满足
return true;
}
//取反
//当农夫不在起点时我们将要考虑河对岸的情况，就是将起点的每一个元素取反
private int[] reverse(int[] arr){
int [] arrSide = new int[arr.length];
for(int i=0;i<arr.length;i++){
if(arr[i]==1)
arrSide[i]=0;
if(arr[i]==0)
arrSide[i]=1;
}
return arrSide;
}
//移动元素
/*
* 农夫尝试带一个元素过河，
* 判断这一步是否有效和安全，
* 如果不安全或不有效
* 就将这一步还原
* 如此循环直到最终状态
*
* */
public void remove(int [] arr){
String[] name={"","猫","狗","鱼"};//方便输出时的表
String [] flagStrs={"过河","回来"};
set(arr,"初始状态");//将初始状态入队列
int flag=0;
while(isEnd(arr)){
if(arr[0]==1){//如果农夫在起点
// 农夫尝试带一个元素过河
for(int i=0;i<arr.length;i++){
//遇到元素不在这里跳过
if(arr[i]==0){
continue;
}
//
arr[0]=0;
arr[i]=0;
//i=0时表示考虑农夫是否是自己过河
if(i==0){
if(isSafe(arr)){
if(flag==1){
if(isVaid(reverse(arr))){
if(flag==1){
arr=reverse(arr);
set(arr, "农夫自己"+flagStrs[flag]);
flag=0;
break;
}else if(flag==0){
set(arr, "农夫自己"+flagStrs[flag]);
flag=1;
break;
}
}
}
}
}
//判断这一步是否有效如果无效就将状态归位，并跳过
if(!isSafe(arr)){
arr[0]=1;
arr[i]=1;
continue;
}
//判断农夫是否这一步是否安
//全如果安全就将这一步入队列
if(isVaid(arr)){
if(flag==1){
arr=reverse(arr);
set(arr,"农夫带着"+name[i]+flagStrs[flag]);
flag=0;
break;
}
if(flag==0){
set(arr,"农夫带着"+name[i]+flagStrs[flag]);
flag=1;
break;
}
}else{
//不安全就将状态归位
arr[0]=1;
arr[i]=1;
}
}
}else{
//农夫不在起点时首先获取对岸情况
arr =reverse(arr);
flag=1;
continue;
}
}
}
public void print(){
remove(l);
for (Iterator<Node> iterator = list.iterator(); iterator.hasNext();) {
Node node = iterator.next();
System.out.println(node);
}
}
private int[] l={1,1,1,1};//数组的每个元素 l[0]农夫，l[1]猫, l[2]狗，l[3]鱼
private ArrayList<Node> list=new ArrayList<Node>(); //步骤队列
public static void main(String[] args) {
Test10 t10=new Test10();
t10.print();
}
}

复制代码