紧急求救啊!
6个人过河问题：
女儿，儿子，父亲，母亲和一个警察，一个犯人，
其中就警察、父亲、母亲会划船
船只能坐2个人
而且父亲离开儿子的时候母亲会打儿子
同样母亲离开女儿时父亲也会打女儿，警察离开犯人会欺负剩下的人
最后怎么能通过河？
请写一个程序来找到解决方案，程序执行后的输出结果可以类似下面这个结果：
1 警察与犯人过去,警察回来...........父亲,母亲,儿子,女儿,警察:对岸:犯人
2 警察与儿子过河,警察带犯人回来..父亲,母亲,女儿,警察,犯人:对岸:儿子
3 母亲与父亲过河,母亲回来..................母亲,女儿,警察,犯人:对岸:儿子,父亲
4 警察与犯人过河,父亲回来.........................母亲,父亲,女儿:对岸:警
察,犯人,儿子
5 母亲与父亲过河,母亲回来................................母亲,女儿:对岸:其他人
6 母亲与女儿过河....
各位高手帮忙啊!
[解决办法]
貌似很浪费时间
[解决办法]
我很同意2楼的意见
很浪费时间
[解决办法]
这种逻辑问题真的不好写,虽然我不会,但是帮你顶吧!希望有高手会!
[解决办法]
花了3个小时弄了一下,发现我没这个时间去做了.呵呵!
貌似很困难的说.
[解决办法]
那天看着挺好玩的,试着编了一下.....费死牛劲了
但愿楼主还能看到.
用法:
1. enum Commuter可以设置渡河者和是否可以划船
2. enum Constrain可以设置限制条件
3. 初始化时候可以设置船容量
4. shuffleBoatableList()用于打乱列表,这样可以得到不同的方案
5. 有可能会出现恶心的死循环,导致stack溢出.这种情况用shuffleBoatableList打乱再试
程序如下: 乱了的话,扔到eclipse里面用ctrl+shift+f
-------------------------------------------
/*以police,criminal,mother,father,son,daughter为例
* 对应的位置号为0,1,2,3,4,5
* 所以所有可能的组合可以对应到二进制111111
* 如只有police, criminal
* 则对应二进制为000011, 对应到十进制为3
* 所以所有状态均可由0~63的int代替
* 然后剔除受限制的int,剩下的就是avaibleList
* 如000110,001010,010010,100010均属受限制的*/
import java.util.*;
public class AcrossRiver {
private int range; //二进制111111(6人)对应的int
private int boatCapacity; //船容量
private int commuterNum; // 渡河者总数
private int constrainNum; // "限制 "总数
//限制(转换后), 如: f(位置3),c(位置1),在p(位置0)条件下共存. 则限制为001010,mask为001011
private int[] constrains;
private int[] mask;
private boolean findFlag; //找到结果的标志
private HashSet <Integer> [] avaibleList; //可供存列表
private ArrayList <Integer> [] boatableList; //船上可供存并且可划船列表
private Commuter[] commuter; //渡河者
private Constrain[] arrayc; //限制(转换前)
private Stack <State> stack; //过程
public static void main(String[] args) {
AcrossRiver ar = new AcrossRiver(2);
ar.shuffleBoatableList();
ar.load(Bank.right, 0);
}
public AcrossRiver(int boatCapacity) {
this.boatCapacity = boatCapacity;
commuter = Commuter.values();
arrayc = Constrain.values();
range = (int)Math.pow(2, commuter.length)-1;
constrainNum = arrayc.length;
commuterNum = commuter.length;
constrains = new int[constrainNum];
mask = new int[constrainNum];
avaibleList = new HashSet[commuterNum];
for(int i=0; i <commuterNum; i++)
avaibleList[i] = new HashSet <Integer> ();
convertConstrain();
initAvaiableList();
boatableList = new ArrayList[boatCapacity+1];
for(int i=1; i <=boatCapacity; i++)
boatableList[i] = new ArrayList <Integer> ();
initBoatableList(boatCapacity);
State initState = new State(0, 0, range);
stack = new Stack <State> ();
stack.add(initState);
boatMaxString = boatMaxString();
bankMaxString = bankMaxString();
}
//乱序boatableList
public void shuffleBoatableList() {
for(int i=1; i <=boatCapacity; i++)
Collections.shuffle(boatableList[i]);
}
//还原
public void reset() {
stack.removeAllElements();
State initState = new State(0, 0, range);
stack.add(initState);
findFlag = false;
}
//限制条件转换
private void convertConstrain() {
for(int i=0; i <arrayc.length; i++) {
int result = 0;
result |= 1 < <arrayc[i].troubleMaker1.ordinal();
result |= 1 < <arrayc[i].troubleMaker2.ordinal();
constrains[i] = result;
result |= 1 < <arrayc[i].coordinator.ordinal();
mask[i] = result;
}
}
//生成船上可供存列表
private void initBoatableList(int boatCapacity) {
for (int j = boatCapacity; j > = 1; j--) {
Iterator <Integer> it = avaibleList[j].iterator();
while (it.hasNext()) {
Integer i = it.next();
for(int k=0; k <commuterNum; k++)
if(((i & 1 < <k) != 0)&&(commuter[k].boatable)) {
boatableList[j].add(i);
break;
}
}
}
}
//生成可供存列表
private void initAvaiableList() {
avaibleList[0].add(0);
label:
for(int i=1; i <range; i++) {
for(int j=0; j <mask.length; j++)
if((i & mask[j]) == constrains[j])
continue label;
avaibleList[numof1(i)].add(i);
}
}
//开始载人...采用递归,对河岸载人时,首先检查 "船上可供存列表 ",从河岸上的人中找出坐船的人
//然后检查剩下的人是否共存
public void load(Bank b, int privious) {
if(stack.empty()) {
System.out.println( "Sorry! no possibility exists! ");
System.exit(0);
}
State state = stack.peek();
if(state.bankL == range) {
findFlag = true;
System.out.println(title());
Iterator it = stack.listIterator();
while(it.hasNext())
System.out.println(it.next());
return;
}
if (b == Bank.right) {
int bankRNum = numof1(state.bankR);
for (int p = boatCapacity; p > = 1; p--) {
for (int i = 0; i < boatableList[p].size(); i++) {
int boat = boatableList[p].get(i);
int bankL = state.bankL;
int bankR = boat ^ state.bankR;
if ((boat != privious)
&& (avaibleList[bankRNum - p].contains(bankR))) {
State newState = new State(bankL, boat, bankR);
stack.push(newState);
newState = new State(bankL + boat, 0, bankR);
stack.push(newState);
//System.out.println(stack);
load(Bank.left, boat);
if(findFlag==true)
return;
stack.pop();
stack.pop();
}
}
}
} else {
int bankLNum = numof1(state.bankL);
for (int p = 1; p <= boatCapacity; p++) {
for (int i = 0; i < boatableList[p].size(); i++) {
int boat = boatableList[p].get(i);
int bankL = boat ^ state.bankL;
int bankR = state.bankR;
if ((boat != privious)
&& (avaibleList[bankLNum - p].contains(bankL))) {
State newState = new State(bankL, boat, bankR);
stack.push(newState);
newState = new State(bankL, 0, bankR + boat);
stack.push(newState);
//System.out.println(stack);
load(Bank.right, boat);
if(findFlag==true)
return;
stack.pop();
stack.pop();
}
}
}
}
}
//过程状态
private class State {
int bankL;
int boat;
int bankR;
State(int bankL, int boat, int bankR) {
this.bankL = bankL;
this.boat = boat;
this.bankR = bankR;
}
public String toString() {
String sBankL = restore(bankL);
String sBoat = restore(boat);
String sBankR = restore(bankR);
return sBankL + bankMaxString.substring(sBankL.length())
+ sBoat + boatMaxString.substring(sBoat.length())
+ sBankR + bankMaxString.substring(sBankR.length());
}
}
//打印对齐用
private String boatMaxString;
private String bankMaxString;
//对齐title用
private String title() {
return "Left Bank: " + bankMaxString.substring( "Left Bank: ".length())
+ "Boat: " + boatMaxString.substring( "Boat: ".length())
+ "Right Bank: " + bankMaxString.substring( "Right Bank: ".length());
}
//打印对齐用
private String boatMaxString() {
int max = commuter[0].toString().length();
for(int i=1; i <commuterNum; i++)
if(commuter[i].toString().length() > max)
max = commuter[i].toString().length();
char[] ac = new char[(max+2) * boatCapacity];
for(int i=0; i <ac.length; i++)
ac[i] = ' ';
return new String(ac);
}
//打印对齐用
private String bankMaxString() {
int length = restore(range).length();
char[] ac = new char[length];
for(int i=0; i <ac.length; i++)
ac[i] = ' ';
return new String(ac);
}
//将int还原为commuter
private String restore(int i) {
ArrayList <Commuter> al = new ArrayList <Commuter> ();
for(int j=0; j <commuterNum; j++)
if((i & 1 < <j) != 0)
al.add(commuter[j]);
return al.toString();
}
//i的二进制中1的个数
private int numof1(int i) {
int num = 0;
for(int j=0; j <commuterNum; j++)
if((i & 1 < <j) != 0)
num++;
return num;
}
//可爱的河岸
private enum Bank {
left, right;
}
}