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]);