import java.util.Arrays;
创新互联公司长期为1000多家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为迎江企业提供专业的成都网站建设、成都网站设计，迎江网站改版等技术服务。拥有10年丰富建站经验和众多成功案例,为您定制开发。
import java.util.List;
import java.util.Stack;
public class Monkey {
public String[] monkeys = { "a", "b", "c", "A", "B", "C" };
Rule rule1 = new Rule1();
Rule rule2 = new Rule2();
public int count = 0;
public StringBuffer success = new StringBuffer(2000);
public void boat() {
StackString left = new StackString();
StackString right = new StackString();
for (int i = 0; i monkeys.length; i++) {
left.add(monkeys[i]);
}
go(left, right, "");
System.out.println("***********************共" + count + "种成功方案***********************");
System.out.println(success.toString());
System.out.println("***********************共" + count + "种成功方案***********************");
}
private void go(StackString left, StackString right, String s) {
for (int i = 0; i left.size(); i++) {
String monkey1 = left.get(i);
for (int j = i + 1; j left.size(); j++) {
StringBuffer sb = new StringBuffer();
String monkey2 = left.get(j);
sb.append(s);
sb.append(monkey1);
sb.append(monkey2);
sb.append("-");
sb.append(" ");
if ((rule1.isCanBoat(monkey1, monkey2, sb)) (rule2.isCanBoat(monkey1, monkey2, sb))) {
StackString nextLeft = new StackString();
StackString nextRight = new StackString();
nextLeft.addAll(left);
nextRight.addAll(right);
nextLeft.remove(monkey1);
nextLeft.remove(monkey2);
nextRight.push(monkey1);
nextRight.push(monkey2);
if (nextLeft.size() == 0) {
success.append(sb.toString() + nextLeft.toString() + nextRight.toString());
success.append("\n");
count++;
continue;
}
back(nextLeft, nextRight, sb.toString());
}
}
}
}
private void back(StackString left, StackString right, String s) {
for (int i = 0; i right.size(); i++) {
String monkey1 = right.get(i);
StringBuffer sb = new StringBuffer();
sb.append(s);
sb.append(monkey1);
sb.append("-");
sb.append(" ");
if (rule2.isCanBoat(monkey1, monkey1, sb)) {
StackString nextLeft = new StackString();
StackString nextRight = new StackString();
nextLeft.addAll(left);
nextRight.addAll(right);
nextLeft.push(monkey1);
nextRight.remove(monkey1);
go(nextLeft, nextRight, sb.toString());
}
}
}
public static void main(String[] args) {
Monkey monkey = new Monkey();
monkey.boat();
}
}
interface Rule {
boolean isCanBoat(String m1, String m2, StringBuffer sb);
}
class Rule1 implements Rule {
String[] childMonkeys = { "a", "b", "c" };
String[] monkeys = { "A", "B", "C" };
public boolean isCanBoat(String m1, String m2, StringBuffer sb) {
if (m1.toLowerCase().equals(m2.toLowerCase())) {
return true;
}
ListString childMonkeysList = Arrays.asList(childMonkeys);
ListString monkeysList = Arrays.asList(monkeys);
if ((monkeysList.contains(m1) monkeysList.contains(m2))
|| (childMonkeysList.contains(m1) childMonkeysList.contains(m2))) {
return true;
}
sb.append("大猴欺负小猴！");
System.out.println(sb.toString());
return false;
}
}
class Rule2 implements Rule {
String[] smartMonkeys = { "A", "B", "C", "a" };
public boolean isCanBoat(String m1, String m2, StringBuffer sb) {
ListString smartMonkeysList = Arrays.asList(smartMonkeys);
if (smartMonkeysList.contains(m1) || smartMonkeysList.contains(m2)) {
return true;
}
sb.append("没有会划船的猴子！");
System.out.println(sb.toString());
return false;
}
}
六种动物过河,是大小虎,大小豹,大小熊,大熊大狮大虎小熊会划船,只有一只船并且一次只能载两只动物,注意，小的旁边如果有其他大的而没有自己大的就会被欺负(大不吃大,小不吃小),怎么能使它们全过河?（最好有原代码提供，谢了~~）
附：
猛兽过河的过程为：
第一步：小熊和小虎过去————小雄回来送船
第二步：小熊和小豹过去————小熊回来送船
第三步：大豹子和大虎过去————大虎和小虎送船
第四步：小熊和大熊过去--------大豹和小豹回来送船
第五步：大豹和大虎过去-------小熊回来送船
第六步：小熊和小虎过去---------小熊回来
第七步:小熊和小豹过去
微软的一条面试题（和猛兽过河问题很相似,供参考）：
三只母鸡，三只小鸡在河东岸，一条小舟每次最多载两只鸡（大小不论）。
条件：
1、母鸡都会划船。
2、只有一只小鸡会划船，其余两只不会。
3、当小鸡母亲不在身边时，其余母鸡就会啄死这只小鸡。
其算法为：
int 过河前数组,把鸡放进去
int 过河后数组
再定义一个结构
{鸡1;
鸡2;
int *pnext;
}
及结构指针
结构指针开辟内存
void 过河(过河前数组,过河后数组,结构指针)
{if(过河前数组全为0)
{输出链表中的内容
return;
}
else
{ int i,j,m,n;
int temp过河前数组;
int temp过河后数组;
temp过河前数组=过河前数组;
temp过河后数组=过河后数组
for(i=0;i上标-1;i++)
for(j=i+1;j上标;j++)
{m=过河前数组[i];
n=过河前数组[j];
if(判取出两个数后剩下的数及这两个数满足过河条件别忘了判这两个数与过河后数组满不满足)
{把m,n放入结构;
if(判结构指针中的pnext是否为null)
是结构指针开辟内存 形成新结构组成链表;
否就把指针向下移;
把m,n放入temp过河后数组
temp过河前数组中把m,n变为0;
回河(temp过河前数组,temp过河后数组,结构指针);
}
}
}
}
void 回河(过河前数组,过河后数组,结构指针)
{int i,j,m,n;
int temp过河前数组;
int temp过河后数组;
int temp结构指针=结构指针;
temp过河前数组=过河前数组;
temp过河后数组=过河后数组;
for(i=0;i上标-1;i++)
for(j=i+1;j上标;j++)
{m=过河后数组[i];
n=过河后数组[j];
if(判取出2个数后剩下的数及这两个数满足回河条件别忘了判这2个数与过河前数组满不满足)
{把m,n放入结构;
if(判结构指针中的pnext是否为null)
是开辟内存 形成新结构组成链表;
否就把指针向下移;
把m,n放入temp过河前数组
temp过河后数组中把m,n变为0;
过河(temp过河前数组,temp过河后数组,结构指针);
}
}
temp过河前数组=过河前数组;
temp过河后数组=过河后数组;
for(i=0;i上标-1;i++)
{m=过河后数组[i];
if(判取出1个数后剩下的数及这1个数满足回河条件别忘了判这1个数与过河前数组满不满足)
{if(判temp结构指针中的pnext是否为null)
是开辟内存 形成新结构组成链表;
否就把指针向下移;
把m放入temp过河前数组
temp过河后数组中把m变为0;
过河(temp过河前数组,temp过河后数组,temp结构指针);
}
}
急求！！！
//CrossRiverQuestion.java
import java.util.ArrayList;
import java.util.List;
public class CrossRiverQuestion {
public static void main(String[] args) {
CrossRiverQuestion q = new CrossRiverQuestion(5, 4);
q.solveQuestion();
}
private int peoNum;
private int savageNum;
private ListNode resultList = new ArrayListNode();
public ListNode solveQuestion() {
Node n = new Node(peoNum,savageNum,0,0,0,new ArrayListInteger(),0,0);
boolean dfsResult = dfs(n);
if(dfsResult) {
resultList.add(0,n);
for(Node node : resultList) {
System.out.println("左岸传教士："+node.getLeftPeo()+"左岸野人： "+node.getLeftSavage()+" 右岸传教士： "+node.getRightPeo()+"右岸野人："+node.getRightSavage()+"船上传教士："+node.getOnBoatPeoNum()+"船上野人："+node.getOnBoatSavageNum());
}
return resultList;
}
return null;
}
public CrossRiverQuestion(int peoNum, int savageNum) {
super();
this.peoNum = peoNum;
this.savageNum = savageNum;
}
private boolean dfs(Node n) {
if(n.hasVisited()) return false;
n.addCheckSum();
if(n.getLeftPeo()==0n.getLeftSavage()==0) return true;
if(n.getLeftPeo()0||n.getRightPeo()0||n.getLeftSavage()0||n.getRightSavage()0) {
return false;
}
if(n.getLeftPeo()n.getLeftSavage()n.getLeftPeo()0) return false;
if(n.getRightPeo()n.getRightSavage()n.getRightPeo()0) return false;
if(n.getCURR_STATE()==n.getStateBoatLeft()) {
Node n1 = new Node(n.getLeftPeo()-1,n.getLeftSavage()-1,n.getRightPeo()+1,n.getRightSavage()+1,n.getStateBoatRight(),n.getNodesCheckSum(),1,1);
if(dfs(n1)) {
resultList.add(0,n1);
return true;
}
Node n4 = new Node(n.getLeftPeo()-2,n.getLeftSavage(),n.getRightPeo()+2,n.getRightSavage(),n.getStateBoatRight(),n.getNodesCheckSum(),2,0);
if(dfs(n4)) {
resultList.add(0,n4);
return true;
}
Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()-2,n.getRightPeo(),n.getRightSavage()+2,n.getStateBoatRight(),n.getNodesCheckSum(),0,2);
if(dfs(n5)) {
resultList.add(0,n5);
return true;
}
}
else {
Node n6 = new Node(n.getLeftPeo(),n.getLeftSavage()+1,n.getRightPeo(),n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),0,1);
if(dfs(n6)) {
resultList.add(0,n6);
return true;
}
Node n7 = new Node(n.getLeftPeo()+1,n.getLeftSavage(),n.getRightPeo()-1,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),1,0);
if(dfs(n7)) {
resultList.add(0,n7);
return true;
}
Node n1 = new Node(n.getLeftPeo()+1,n.getLeftSavage()+1,n.getRightPeo()-1,n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),1,1);
if(dfs(n1)) {
resultList.add(0,n1);
return true;
}
Node n4 = new Node(n.getLeftPeo()+2,n.getLeftSavage(),n.getRightPeo()-2,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),2,0);
if(dfs(n4)) {
resultList.add(0,n4);
return true;
}
Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()+2,n.getRightPeo(),n.getRightSavage()-2,n.getStateBoatLeft(),n.getNodesCheckSum(),0,2);
if(dfs(n5)) {
resultList.add(0,n5);
return true;
}
}
return false;
}
public ListNode getResultList() {
return resultList;
}
}
Node.java
import java.util.ArrayList;
import java.util.List;
public class Node {
private ListInteger nodesCheckSum = new ArrayListInteger();
private int leftPeo;
private int rightPeo;
private int leftSavage;
private int rightSavage;
private int CURR_STATE = 0;
private int onBoatPeoNum = 0;
private int onBoatSavageNum = 0;
private final int STATE_BOAT_LEFT = 0;
private final int STATE_BOAT_RIGHT = 1;
public Node(int leftPeo, int leftSavage, int rightPeo, int rightSavage, int state, List checkSumList, int onBoatPeoNum, int onBoatSavageNum) {
this.CURR_STATE = state;
this.leftPeo = leftPeo;
this.leftSavage = leftSavage;
this.rightPeo = rightPeo;
this.rightSavage = rightSavage;
this.nodesCheckSum.addAll(checkSumList);
this.onBoatPeoNum = onBoatPeoNum;
this.onBoatSavageNum = onBoatSavageNum;
}
public int getLeftPeo() {
return leftPeo;
}
public void setLeftPeo(int leftPeo) {
this.leftPeo = leftPeo;
}
public int getRightPeo() {
return rightPeo;
}
public void setRightPeo(int rightPeo) {
this.rightPeo = rightPeo;
}
public int getLeftSavage() {
return leftSavage;
}
public void setLeftSavage(int leftSavage) {
this.leftSavage = leftSavage;
}
public int getRightSavage() {
return rightSavage;
}
public void setRightSavage(int rightSavage) {
this.rightSavage = rightSavage;
}
@Override
public String toString() {
return leftPeo+","+leftSavage+","+rightPeo+","+rightSavage+","+CURR_STATE;
}
public int getCURR_STATE() {
return CURR_STATE;
}
public void setCURR_STATE(int cURR_STATE) {
CURR_STATE = cURR_STATE;
}
public int getStateBoatLeft() {
return STATE_BOAT_LEFT;
}
public int getStateBoatRight() {
return STATE_BOAT_RIGHT;
}
public int calcCheckSum() {
return 1*getCURR_STATE()+10*getLeftPeo()+100*getLeftSavage()+1000*getRightPeo()+10000*getRightSavage();
}
public void addCheckSum() {
int checkSum = calcCheckSum();
nodesCheckSum.add(checkSum);
}
public boolean hasVisited() {
int sum = calcCheckSum();
for (Integer checkSum : nodesCheckSum) {
if(checkSum==sum) return true;
}
return false;
}
public ListInteger getNodesCheckSum() {
return nodesCheckSum;
}
public int getOnBoatPeoNum() {
return onBoatPeoNum;
}
public void setOnBoatPeoNum(int onBoatPeoNum) {
this.onBoatPeoNum = onBoatPeoNum;
}
public int getOnBoatSavageNum() {
return onBoatSavageNum;
}
public void setOnBoatSavageNum(int onBoatSavageNum) {
this.onBoatSavageNum = onBoatSavageNum;
}
}
