三只大老虎和三只小老虎过河
三只大老虎和三只小老虎过河
三只大老虎分别是A.B.C三只小老虎分别是1.2.3,只有一条船,一次只能坐两只,A和1是母子俩,B和2是母子俩,C和3母子俩,只要任何一个母亲离开小老虎,小老虎都会被吃掉.
问题补充：大老虎都会划船 三只小老虎中只有1会划船
设大老虎为ABC，相应的小老虎为abc，其中c会划船。
package test;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TigerRiver {
public static int[]tigersteps=new int[27*27*3] ;
public static Map<Integer,Status> map = new HashMap<Integer,Status>();
int i=0;
public TigerRiver() {
Status status = new Status(2, 2, 2, 2, 2, 2,false);
for(int i=0;i<tigersteps.length;i++){
tigersteps[i]=-1;
}
map.put(status.hashCode(), status);
tigersteps[status.hashCode()]=0;
}
public int minStep(Status status) throws IllegalArgumentException, IllegalAccessException {
int hascode=status.hashCode();
int minstep = tigersteps[hascode];
if (minstep != -1)
return minstep;
minstep = Integer.MAX_VALUE;
map.put(hascode, status);
List<Status> steps = status.getAllStep();
for (Status status2 : steps) {
int temhascode=status2.hashCode();
if(tigersteps[temhascode]==-1 && map.get(temhascode)!=null)continue;
int temstep = minStep(status2);
if (temstep < minstep-1) {
minstep = temstep+1;
status.setNextStatus(map.get(temhascode));
}
}
tigersteps[hascode]=minstep;
return minstep;
}
public static void print(Status status){
System.out.println(status);
while (status.getNextStatus()!=null) {
status=status.getNextStatus();
System.out.println(status);
}
}
public static void main(String[] args) {
Status status = new Status(0, 0, 0, 0, 0, 0,true);
TigerRiver tigerRiver=new TigerRiver();
try {
System.out.println("steps:"+tigerRiver.minStep(status));
} catch (IllegalArgumentException e) {
e.printStackTrace();
} catch (IllegalAccessException e) {
e.printStackTrace();
}
print(status);
}
}
package test;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;
import org.apache.poi.hssf.record.ContinueRecord;
public class Status {
public int A;
public int a;
public int B;
public int b;
public int C;
public int c;
private boolean left;
private Status nextStatus;
public Status(int big1, int small1, int big2, int small2, int big3,
int small3, boolean left) {
super();
this.A = big1;
this.a = small1;
this.B = big2;
this.b = small2;
this.C = big3;
this.c = small3;
this.left = left;
}
public Status(Status status) {
super();
this.A = status.A;
this.a = status.a;
this.B = status.B;
this.b = status.b;
this.C = status.C;
this.c = status.c;
this.left = status.left;
}
public List<Status> getAllStep() throws IllegalArgumentException,
IllegalAccessException {
List<Status> steps = new ArrayList<Status>();
if (left) {
List<Status> atob = getOneStepTrigers(0, 1);
for (Status status : atob) {
if (status.check())
steps.add(status);
}
List<Status> btoa = getOneStepTrigers(1, 0);
for (Status status : btoa) {
if (status.check())
steps.add(status);
}
if(getCount(0)>=2){
List<Status> atwob = getTwoStepTrigers(0, 1);
for (Status status : atwob) {
if (status.check())
steps.add(status);
}
}
if(getCount(1)>=2){
List<Status> btwoa = getTwoStepTrigers(1, 0);
for (Status status : btwoa) {
if (status.check())
steps.add(status);
}
}
} else {
List<Status> ctob = getOneStepTrigers(2, 1);
for (Status status : ctob) {
if (status.check())
steps.add(status);
}
List<Status> btoc = getOneStepTrigers(1, 2);
for (Status status : btoc) {
if (status.check())
steps.add(status);
}
if(getCount(2)>=2){
List<Status> ctwob = getTwoStepTrigers(2, 1);
for (Status status : ctwob) {
if (status.check())
steps.add(status);
}
}
if(getCount(1)>=2){
List<Status> btwoc = getTwoStepTrigers(1, 2);
for (Status status : btwoc) {
if (status.check())
steps.add(status);
}
}
}
if (A == 1 || B == 1 || C == 1 || c == 1) {
Status status = new Status(this);
status.left = !left;
steps.add(status);
}
return steps;
}
public boolean check() {
if (A < 0 || B < 0 || C < 0 || a < 0 || b < 0 || c < 0)
return false;
if (a == 0 && A != 0 || b == 0 && B != 0 || c == 0 && C != 0) {
if (A == 0 || B == 0 || C == 0) {
return false;
}
}
if (getCount(1) > 2)
return false;
if (a == 1 && A != 1 || b == 1 && B != 1 || c == 1 && C != 1) {
if (A == 1 || B == 1 || C == 1) {
return false;
}
}
if (a == 2 && A != 2 || b == 2 && B != 2 || c == 2 && C != 2) {
if (A == 2 || B == 2 || C == 2) {
return false;
}
}
return true;
}
private List<Field> getTrigers(int point) throws IllegalArgumentException,
IllegalAccessException {
List<Field> trigers = new ArrayList<Field>();
Field[] fields = this.getClass().getFields();
for (Field field : fields) {
if (((Integer) field.get(this)).intValue() == point) {
trigers.add(field);
}
}
return trigers;
}
private List<Status> getOneStepTrigers(int from, int to)
throws IllegalArgumentException, IllegalAccessException {
List<Status> trigers = new ArrayList<Status>();
List<Field> fList = getTrigers(from);
for (Field field : fList) {
Status status = new Status(this);
field.set(status, to);
trigers.add(status);
}
return trigers;
}
private List<Status> getTwoStepTrigers(int from, int to)
throws IllegalArgumentException, IllegalAccessException {
List<Status> trigers = new ArrayList<Status>();
List<Field> fList = getTrigers(from);
for (int i = 0; i < fList.size() - 1; i++) {
for (int j = i + 1; j < fList.size(); j++) {
Field fielda = fList.get(i);
Field fieldb = fList.get(j);
Status status = new Status(this);
fielda.set(status, to);
fieldb.set(status, to);
trigers.add(status);
}
}
return trigers;
}
private int getCount(int point) {
int count = 0;
if (A == point)
count++;
if (B == point)
count++;
if (C == point)
count++;
if (a == point)
count++;
if (b == point)
count++;
if (c == point)
count++;
return count;
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
if (A == 0)
sb.append("A");
if (B == 0)
sb.append("B");
if (C == 0)
sb.append("C");
if (a == 0)
sb.append("a");
if (b == 0)
sb.append("b");
if (c == 0)
sb.append("c");
for (int i = getCount(0); i < 6; i++) {
sb.append(" ");
}
sb.append(" | ");
if (!left) {
sb.append(" ");
}
if (A == 1)
sb.append("A");
if (B == 1)
sb.append("B");
if (C == 1)
sb.append("C");
if (a == 1)
sb.append("a");
if (b == 1)
sb.append("b");
if (c == 1)
sb.append("c");
for (int i = getCount(1); i < 2; i++) {
sb.append(" ");
}
if (left) {
sb.append(" ");
}
sb.append(" | ");
if (A == 2)
sb.append("A");
if (B == 2)
sb.append("B");
if (C == 2)
sb.append("C");
if (a == 2)
sb.append("a");
if (b == 2)
sb.append("b");
if (c == 2)
sb.append("c");
for (int i = getCount(0); i < 6; i++) {
sb.append(" ");
}
return sb.toString();
}
public Status getNextStatus() {
return nextStatus;
}
public void setNextStatus(Status nextStatus) {
this.nextStatus = nextStatus;
}
@Override
public int hashCode() {
int prime = 1;
int result = 0;
result += prime * A;
prime *= 3;
result += prime * a;
prime *= 3;
result += prime * B;
prime *= 3;
result += prime * b;
prime *= 3;
if (left) {
result += prime * 1;
} else {
result += prime * 2;
}
prime *= 3;
result += prime * C;
prime *= 3;
result += prime * c;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Status other = (Status) obj;
if (A != other.A)
return false;
if (B != other.B)
return false;
if (C != other.C)
return false;
if (left != other.left)
return false;
if (nextStatus == null) {
if (other.nextStatus != null)
return false;
} else if (!nextStatus.equals(other.nextStatus))
return false;
if (a != other.a)
return false;
if (b != other.b)
return false;
if (c != other.c)
return false;
return true;
}
}
steps:27
ABCabc | |
ABab | Cc |
ABab | Cc |
ABab | C | c
ABab | C | c
ABCab | | c
ACa | Bb | c
ACa | Bb | c
ACa | B | bc
ACa | B | bc
Aa | BC | bc
Aa | BC | bc
Aa | | BCbc
Aa | Bb | Cc
Aa | Bb | Cc
ABab | | Cc
ab | AB | Cc
ab | AB | Cc
ab | A | BCc
ab | A | BCc
b | Aa | BCc
b | Aa | BCc
b | | ABCac
b | B | ACac
b | B | ACac
| Bb | ACac
| Bb | ACac
| | ABCabc public class Status { String status; List<Status> children; Status(String s){ status = s; } public void getAllChildrenStatus(){ //解析status字符串，找到其所有下一步 //放入到children队列中 ....... } public eques(){...} public hashcode(){...}}public class StatusManager{ private Status startStatus; private Status endStatus; StatusManager(Status start,Status end){ startStatus = start; endStatus = end; } // 记录当前所走过的路径，避免重复 // 如 A->B->C->....A->B->C->A // 每一种状态最多只出现一次 private static List moveRecord<Status> = new ArrayList(); //判断当前状态是否已经走过 public boolean RecordHave(Status s){...} public void StatusSearch(){ StatusSearch(startStatus); } public void StatusSearch(Status currentNode){ moveRecord.add(curstatus); currentNodegetAllChildrenStatus(); //遍历所有孩子 for(Status s : currentNode.children){ // 如果孩子已经在moveRecord中，那么我们之前走到过这一步 // 如果和endNode相等，则为所求路径，打印 :) // 递归 if(!RecordHave(s)){ if(s.equals(endNode){ // print all value in current list; // 找到所有的路径，这可能只是其中一种 ........ continue; } StatusSearch(s); } } //回到上一步 moveRecord.remove(moveRecord.size()); } }module Main whereimport Listimport Maybeimport Text.Printfmain = putStrLn $ prettyPrintPath $ fromJust $ bfsdata Tiger = BigA | BigB | BigC | SmallA | SmallB | SmallC deriving (Show,Eq,Ord)-- SmallC can drive boat-- A helper logical function: a implies bimplies :: Bool -> Bool -> Boolimplies a b = (not a) || bdata State = State Place [Tiger] deriving (Show,Eq)data Trans = Trans [Tiger] deriving (Show,Eq)data Place = Local | Remote deriving (Show,Eq)allTigers = [BigA,BigB,BigC,SmallA,SmallB,SmallC]bigTigers = [BigA,BigB,BigC]smallTigers = [SmallA,SmallB,SmallC]driverTigers = [BigA,BigB,BigC,SmallC]startingState = State Local allTigersfinalState = State Remote []-- A state is valid if both side of river is validstateValid :: State -> BoolstateValid (State _ tigers) = localStateValid tigers && localStateValid (allTigers\\tigers) where -- A state is valid on one side of river means -- Either there are no big tigers or all small tigers are protected by their mothers localStateValid tigers = (noBigTiger tigers) || (allProtected tigers) noBigTiger tigers = all (`notElem` tigers) bigTigers allProtected tigers = all protected (zip smallTigers bigTigers) where protected (small,big) = (small `elem` tigers) `implies` (big `elem` tigers)-- A transition is valid if there is at most 2 tigers on the boat-- and at least one of them can drive the boat.transValid :: Trans -> BooltransValid (Trans tigers) = length tigers <=2 && any (`elem` tigers) driverTigers-- Find all possible transition from one state,-- no matter whether the target state is valid.findAllTrans :: State -> [Trans]findAllTrans (State place tigers) = map Trans (if place==Local then allTransLocal tigers else allTransLocal (allTigers\\tigers) ) where allTransLocal :: [Tiger] -> [[Tiger]] allTransLocal tigers = let (drivers,others) = partition (`elem` driverTigers) tigers in [[one] | one <- drivers] ++ [[one,another] | one <- drivers, another <- others] ++ anyTwo drivers where anyTwo [] = [] anyTwo [x] = [] anyTwo (x:xs) = [[x,another] | another <- xs] ++ anyTwo xs-- Actually perform one transition on a state, return the target state.-- Tiger lists are sorted for easy comparison.doTrans :: State -> Trans -> StatedoTrans (State Local tigers) (Trans goTigers) = State Remote (sort (tigers\\goTigers))doTrans (State Remote tigers) (Trans comeTigers) = State Local (sort (tigers++comeTigers))-- Breadth first search.-- Search from the initial state to the final statebfs :: Maybe [(State,Trans,State)]bfs = bfs' [startingState] [] []-- Inside algorithmbfs' :: [State] -> [State] -> [(State,Trans,State)] -> Maybe [(State,Trans,State)]bfs' [] _ _ = Nothing -- When queue empty, fail.bfs' (s:ss) visited transes = -- s is current state, ss are other states. if s == finalState -- When final state reached, success. then Just (extractPath transes) else if s `elem` visited -- If state visited or visited, discard. then bfs' ss visited transes else let newVisited = s:visited -- Otherwise mark this state visited. allValidTransition = -- Find all transitions from current state (s), filtered. let allTrans = findAllTrans s allNewStates = map (doTrans s) allTrans in filter (\(s,t,s') -> (stateValid s' && s' `notElem` newVisited)) (zip3 (repeat s) allTrans allNewStates) -- only keep valid and unvisited newFrontier = ss ++ (map (\(s,t,s') -> s') allValidTransition) -- update queue newTranses = allValidTransition ++ transes -- update transition tree in bfs' newFrontier newVisited newTranses -- next round -- Given a resulting transition tree (a list of (State,Trans,State))-- Output a path from startingState to finalStateextractPath sts = reverse $ extractPath' sts finalStateextractPath' _ curState | curState == startingState = []extractPath' sts curState = let (prevState,trans,_) = (fromJust $ find (\(s,t,s') -> s' == curState) sts) in (prevState,trans,curState):(extractPath' sts prevState)-- Pretty print path: print all step and the final stateprettyPrintPath sts = unlines $ ((map prettyPrintStep sts) ++ [prettyPrintStateLine $ (\(_,_,s') -> s') $ last sts])-- Each step consists of the old state and the transitionprettyPrintStep (s,t,s') = (prettyPrintStateLine s) ++ "\n" ++ (prettyPrintTransLine s t)prettyPrintStateLine (State place tigers) = let lhs = prettyPrintTigers tigers rhs = prettyPrintTigers (allTigers\\tigers) stateLine = printf "[%6s] | | [%6s]\n" lhs rhs :: String in stateLineprettyPrintTransLine (State place oldTigers) (Trans movingTigers) = let moves = prettyPrintTigers movingTigers transLine = case place of Local -> printf " %2s --->" moves :: String Remote -> printf " <--- %2s" moves :: String in transLineprettyPrintTigers = map prettyPrintTigerprettyPrintTiger tiger = case tiger of BigA -> 'A' BigB -> 'B' BigC -> 'C' SmallA -> '1' SmallB -> '2' SmallC -> '3'
25 楼 justcol 2009-01-20 写来写去都成了2只小老虎会划船了，貌似原题是只有一只小老虎会划船吧？ 26 楼 liuzhaodong89 2009-01-21 ab | A | BCc
ab | A | BCc
b | Aa | BCc
这种情况b不会被吃掉么.... 27 楼 regale 2009-01-21 liuzhaodong89 写道ab | A | BCc
ab | A | BCc
b | Aa | BCc
这种情况b不会被吃掉么....
这是第一版本，没有考虑主动进攻，第二版已经修正了
steps:38
ABCabc | |
ACac | Bb |
ACac | Bb |
ACac | B | b
ACac | B | b
ABCac | | b
ABC | ac | b
ABC | ac | b
ABC | c | ab
ABC | c | ab
ABCc | | ab
Cc | AB | ab
Cc | AB | ab
Cc | | ABab
Cc | Aa | Bb
Cc | Aa | Bb
ACc | a | Bb
AC | ac | Bb
ACa | c | Bb
Aa | Cc | Bb
Aa | Cc | Bb
Aa | c | BCb
Aa | bc | BC
Aa | b | BCc
Aa | Bb | Cc
Aa | Bb | Cc
ABab | | Cc
ab | AB | Cc
ab | AB | Cc
ab | | ABCc
ab | c | ABC
ab | c | ABC
b | ac | ABC
b | ac | ABC
b | c | ABCa
b | c | ABCa
| bc | ABCa
| bc | ABCa
| | ABCabc
28 楼 ant_miracle 2009-01-23 http://www.blogjava.net/xmatthew/archive/2008/11/16/240766.html
这个是本人用Java的实现。 29 楼 孤灯渡漠 2009-01-23 这样的题好像蛮多的啊，农民、羊、草也是这样类的问题好像 30 楼 sonic39 2009-01-25 很有问题！
ACa | Bb | c
ACa | Bb | c
ACa | B | bc
这一步难道B不会吃掉c？ 31 楼 zookie 2009-01-27 哈哈哈哈哈
