论坛首页 → 入门技术论坛 →

三只大老虎和三只小老虎过河

浏览 19349 次
锁定老帖子 主题：三只大老虎和三只小老虎过河
精华帖 (6) :: 良好帖 (0) :: 新手帖 (2) :: 隐藏帖 (6)
作者 正文
  • regale
  • 等级: 初级会员
  • 性别:
  • 文章: 34
  • 积分: 60
  • 来自: 武汉
   发表时间：2009-01-13  
三只大老虎和三只小老虎过河
三只大老虎分别是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   
返回顶楼
         
  • ahrhu
  • 等级: 初级会员
  • 性别:
  • 文章: 23
  • 积分: 30
  • 来自: 长沙
   发表时间：2009-01-13  
我看不明白
返回顶楼
          回帖地址
0 请登录后投票
  • ahrhu
  • 等级: 初级会员
  • 性别:
  • 文章: 23
  • 积分: 30
  • 来自: 长沙
   发表时间：2009-01-13  
不过我想应该是很有意思的吧
返回顶楼
          回帖地址
0 请登录后投票
  • amozon
  • 等级: 初级会员
  • 性别:
  • 文章: 190
  • 积分: 66
  • 来自: 上海
   发表时间：2009-01-13  
Step 8: B will eat c
那步应该是 ab过去，而不是Bb....
返回顶楼
          回帖地址
0 请登录后投票
  • regale
  • 等级: 初级会员
  • 性别:
  • 文章: 34
  • 积分: 60
  • 来自: 武汉
   发表时间：2009-01-13  
就大C，大老虎，不是小老虎
返回顶楼
          回帖地址
0 请登录后投票
  • amozon
  • 等级: 初级会员
  • 性别:
  • 文章: 190
  • 积分: 66
  • 来自: 上海
   发表时间：2009-01-13  
ACa     | Bb              | c 
ACa     |             Bb  | c 
ACa     |             B   | bc  

这样 B 会吃掉 c
返回顶楼
          回帖地址
0 请登录后投票
  • amozon
  • 等级: 初级会员
  • 性别:
  • 文章: 190
  • 积分: 66
  • 来自: 上海
   发表时间：2009-01-13  
ABCabc  |                 |
ABab    | Cc              | 
ABab    |             Cc  | 
ABab    |             C   | c
ABab    | C               | c
ABCab   |                 | c
ABC     | ab              | c 
ABC     |             ab  | c 
ABC     |             a   | bc 
ABC     | a               | bc 
Aa      | BC              | bc  
Aa      |             BC  | bc  
Aa      |                 | BCbc  
Aa      |             Bb  | Cc  
Aa      | Bb              | Cc  
ABab    |                 | Cc
ab      | AB              | Cc  
ab      |             AB  | Cc  
ab      |             c   | ABC  
ab      | c               | ABC  
b       | ac              | ABC   
b       |             c   | ABCa   
b       | c               | ABCa    
返回顶楼
          回帖地址
0 请登录后投票
  • amozon
  • 等级: 初级会员
  • 性别:
  • 文章: 190
  • 积分: 66
  • 来自: 上海
   发表时间：2009-01-13  
没看到你还有只有c会划船，那么只要开始的Cc改成Aa,或者Bb
返回顶楼
          回帖地址
0 请登录后投票
  • regale
  • 等级: 初级会员
  • 性别:
  • 文章: 34
  • 积分: 60
  • 来自: 武汉
   发表时间：2009-01-13  
你的意思是B会主动上岸去吃c?如果这样，我把判断再改动一下
返回顶楼
          回帖地址
0 请登录后投票
  • regale
  • 等级: 初级会员
  • 性别:
  • 文章: 34
  • 积分: 60
  • 来自: 武汉
   发表时间：2009-01-13  
三只大老虎和三只小老虎过河
三只大老虎分别是A.B.C三只小老虎分别是1.2.3,只有一条船,一次只能坐两只,A和1是母子俩,B和2是母子俩,C和3母子俩,只要任何一个母亲离开小老虎,小老虎都会被吃掉.
问题补充：大老虎都会划船 三只小老虎中只有1会划船
设大老虎为ABC，相应的小老虎为abc，其中c会划船。
再加一个条件，大老虎会主动上岸攻击小老虎

程序说明0表示老虎在左岸，1在船上，2在右岸
Status 表示某个时间点的快照 
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 (a == 0 && A ==2 || b == 0 && B ==2  || c == 0 && C == 2) {
			if (A == 1 || B == 1 || C == 1) {
				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;
			}
		}
		if (a == 2 && A == 0 || b == 2 && B == 0 || c == 2 && C == 0) {
			if (A == 1 || B == 1 || C == 1) {
				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: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     
返回顶楼
          回帖地址
6 请登录后投票
论坛首页 → 入门技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics