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 List<Node> resultList = new ArrayList<Node>()
public List<Node> solveQuestion() {
Node n = new Node(peoNum,savageNum,0,0,0,new ArrayList<Integer>(),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()==0&&n.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 List<Node> getResultList() {
return resultList
}
}
Node.java
import java.util.ArrayListimport java.util.List
public class Node {
private List<Integer> nodesCheckSum = new ArrayList<Integer>()
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 List<Integer> 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
}
}
完全无难度野人位置（X），河宽长（w）
过河方法：
runrain（x,y）{
if(x<=w){
x++
}else（）{
x=w//刚过完河位置
}
