我觉得中间环节有点繁琐，
package com.itheima;
import java.util.Scanner;
/**
* 第10题： 一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。
* 当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，
* 则不会发生这种问题。编程解决猫狗鱼过河问题。
*/
import java.util.Vector;
/**第10题： 一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。
* 当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。
* 编程解决猫狗鱼过河问题。
*
* @author Administrator
*
*/
public class Test10 {
public static Vector<Pos> path;
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner cin=new Scanner(System.in);
Side side=new Side();
path=side.move(0);
if(path!=null){
for(int i=path.size()-1;i>=0;i--){
int n=(path.size()-i-1);
System.out.println("第"+n+"步:");
display(path.get(i).dog_here, "dog"); //输出函数
display(path.get(i).cat_here, "cat ");
display(path.get(i).fish_here, "fish");
display(path.get(i).man_here,"man");
}
}else{
System.out.println("no result");
}
int input=cin.nextInt();
}
public static void display(Boolean b,String s){
if(!b){
System.out.println(" | |"+s);
}else{
System.out.println(s+" | | ");
}
}
}
class Side{ //定义一个Side类，4个boolean分别表示狗，猫，鱼，人的位置，ture表示在原来那边，false表示在对岸
public boolean dog_here=true;
public boolean cat_here=true;
public boolean fish_here=true;
public boolean man_here=true;
public Vector<Pos> path; //当按照规则成功到达对岸时，用于保存移动的路径
public int pathlength; //用于存储移动路径的长度，即步数
public static final int maxpath=10; //当步数过大依然没结果时终止程序，防止无限递归
public Side(Pos pos){ //接受前一个位置状态Pos的构造函数
this.dog_here=pos.dog_here;
this.cat_here=pos.cat_here;
this.fish_here=pos.fish_here;
this.man_here=pos.man_here;
}
public Side(){}
public boolean all_animal_alive(){ //判断当前状态下所有动物是否都活着，
return!(((dog_here)&&(cat_here)&&(!man_here))||
((!dog_here)&&(!cat_here)&&(man_here))||
((fish_here)&&(cat_here)&&(!man_here))||
((!fish_here)&&(!cat_here)&&(man_here)));
}
public boolean success(){ //判断是否全部都到了对岸
return!(dog_here||cat_here||fish_here||man_here);
}
public Vector<Pos> move(int pathlength){ //用于寻找下一个可能的状态，当该路径失败时返回null，成功则返回状态
pathlength++;
if(pathlength>=maxpath) //递归过深则停止
return null;
if(this.all_animal_alive()){ //只有当当前状态下所有动物都活着才有必要下一步
if(success()){ //当成功时返回一个path路径，并将本次状态pos作为第一个元素
path=new Vector<>();
path.add(new Pos(dog_here, cat_here, fish_here, man_here));
return path;
}
Vector<Vector<Pos>> path_group=new Vector<>();
/* 任何状态下下一个移动都只有4种可能性:
* （1）狗和人在同一边，向另一边移动；
* （2）猫和人在同一边，向另一边移动；
* （3）鱼和人在同一边，向另一边移动；
* （4）人单独从对岸向原岸移动。
* path_group用于保存4种可能性下的路径，失败则为null
* 从不为null的路径中选择最短路径返回到上一层调用
*/
if((man_here&&fish_here)||(((!man_here)&&(!fish_here)))){
Pos pos2=new Pos(dog_here, cat_here, !fish_here, !man_here);
Side side2=new Side(pos2);
path_group.add(side2.move(pathlength));
}
if((man_here&&dog_here)||(((!man_here)&&(!dog_here)))){
Pos pos3=new Pos(!dog_here, cat_here, fish_here, !man_here);
Side side3=new Side(pos3);
path_group.add(side3.move(pathlength));
}
if((man_here&&cat_here)||(((!man_here)&&(!cat_here)))){
Pos pos4=new Pos(dog_here, !cat_here, fish_here, !man_here);
Side side4=new Side(pos4);
path_group.add(side4.move(pathlength));
}
if(!man_here){
Pos pos5=new Pos(dog_here, cat_here, fish_here, !man_here);
Side side5=new Side(pos5);
path_group.add(side5.move(pathlength));
}
Vector<Pos> result=null;
int minpath=maxpath+1;
for(int i=0;i<path_group.size();i++){
if(path_group.get(i)!=null){ //挑选出不为null的最短路径并把自己的状态添加到路径末尾
if(minpath>path_group.get(i).size()){
minpath=path_group.get(i).size();
result=path_group.get(i);
}
}
}
if(result!=null){
Pos this_pos=new Pos(dog_here, cat_here, fish_here, man_here);
result.add(this_pos);
return result;
} //把路径返回到上一层调用
}
return null; //当有动物死去则失败返回null
}
}
class Pos{ //pos类，用于存储状态
public boolean dog_here=true;
public boolean cat_here=true;
public boolean fish_here=true;
public boolean man_here=true;
public Pos(Boolean dog,Boolean cat,Boolean fish,Boolean man){
this.dog_here=dog;
this.cat_here=cat;
this.fish_here=fish;
this.man_here=man;
}
} |
|
收藏
淘帖
踩
