编程题：java实现4人在17分钟内过桥

痛定思痛。 2022-05-15 12:51 118阅读 0赞

### 题目： ###

怎么让这4个人在17分钟内要过桥  
有4个人要过一座桥.她们都站在桥的某一边,要让她们在17分钟内全部通过这座桥.这时是晚上.她们只有一个手电筒.最多只能让两个人同时过桥.不管是谁过桥,不管是一个人还是两个人,必须要带着手电筒.手电筒必须要传来传去,不能扔过去.每个人过桥的速度不同,两个人的速度必须以较慢的那个人的速度过桥.  
　　第一个人：过桥需要1分钟；  
　　第二个人：过桥需要2分钟；  
　　第三个人：过桥需要5分钟；  
　　第四个人：过桥需要10分钟.  
　　比如,如果第一个人与第4个人首先过桥,等她们过去时,已经过去了10分钟.如果让第4个人将手电筒送回去,那么等她到达桥的另一端时,总共用去了20分钟,行动也就失败了.怎样让这4个人在17分钟内过桥?还有别的什么方法?

### 代码： ###

package parking;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    /**
     * 过桥事件
     * 
     * @author ASUS
     *
     */
    public class CrossBridge {
    
    	private static final String COMMA = ",";
    	// 过桥规定时间不得多于17分钟
    	private static final int SCHEDULT_TIME = 17;
    	private static final String LEFT_SYMBOL = "{";
    	private static final String RIGHT_SYMBOL = "}";
    	private static final String GO_WORD = "过桥去了";
    	private static final String BACK_WORD = "我又返回了";
    	private static final String LEFT_ALLOW = "--->";
    	private static final String RIGHT_ALLOW = "<---";
    	private static final String NEW_LINE = "\n";
    
    	private static int count = 1;
    
    	private static Map<String, Integer> map = new HashMap<>();
    
    	static {
    		map.put("A", 1);
    		map.put("B", 2);
    		map.put("C", 5);
    		map.put("D", 10);
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		List<String> list = new ArrayList<>();
    		list.add("A");
    		list.add("B");
    		list.add("C");
    		list.add("D");
    		StringBuffer sb = new StringBuffer();
    		int initTime = 0;
    		new CrossBridge().resultCross(list, new ArrayList<String>(), initTime, sb);
    	}
    
    	/**
    	 * 处理过桥事件
    	 * 
    	 * @param listNot
    	 *            未过桥人员列表
    	 * @param ListOver
    	 *            已过桥人员列表
    	 * @param initTime
    	 *            花费的时间
    	 * @param sb
    	 *            记录步骤过程
    	 */
    	private void resultCross(List<String> listNot, List<String> ListOver, int initTime, StringBuffer sb) {
    
    		// 获取未过桥的所有两两组合的可能组合
    		List<String> result = getAllResult(listNot);
    
    		for (String groupPeople : result) {
    			// 因为列表数据是【a,b a,c a,d】这种格式
    			String[] peoples = groupPeople.split(COMMA);
    			//表示未过桥的人员列表
    			List<String> current = new ArrayList<>(listNot);
    			//表示已过桥的人员列表
    			List<String> over = new ArrayList<>(ListOver);
    			int currentTime = initTime;
    			StringBuffer currentBuffer = sb;
    			// 过桥后人数变动
    			for (String people : peoples) {
    				// 未过桥列表减去过桥人员
    				current.remove(people);
    				// 已过桥列表增加过桥人员
    				over.add(people);
    			}
    
    			currentTime += getMaxTime(peoples);
    			// 记录一条步骤--》{a,b}--->过桥去了
    			currentBuffer.append(current).append(LEFT_ALLOW).append(LEFT_SYMBOL).append(groupPeople).append(RIGHT_SYMBOL).append(GO_WORD).append(LEFT_ALLOW).append(over).append(NEW_LINE);
    			// 人员全部过完情况
    			if (current.isEmpty()) {
    
    				if (currentTime <= SCHEDULT_TIME) {
    					System.out.println("第" + count + "种情况:");
    					System.out.println("花费时间--》" + currentTime);
    					System.out.println("步骤详情--》");
    					System.out.println(currentBuffer.toString());
    					count++;
    				}
    			} else {
    				// 没有全部过桥情况，得从过桥列表中返回一个人
    				for (String peopleToBack : over) {
    					//表示已过桥的人员列表
    					List<String> overGroup = new ArrayList<>(over);
    					//表示未过桥的人员列表
    					List<String> waitGroup = new ArrayList<>(current);
    					int nowTime = currentTime;
    					StringBuffer nowBuffer = new StringBuffer(currentBuffer.toString());
    					// 已过桥列表删除返回的人员
    					overGroup.remove(peopleToBack);
    					// 未过桥列表增加返回的人员
    					waitGroup.add(peopleToBack);
    					// 加上返回时间
    					nowTime += map.get(peopleToBack);
    
    					// 返回的步骤
    					nowBuffer.append(waitGroup).append(RIGHT_ALLOW).append(LEFT_SYMBOL).append(peopleToBack).append(RIGHT_SYMBOL).append(BACK_WORD)
    					.append(RIGHT_ALLOW).append(overGroup).append(NEW_LINE);
    					// 递归，重新重复以上步骤
    					resultCross(waitGroup, overGroup, nowTime, nowBuffer);
    				}
    
    			}
    
    		}
    
    	}
    
    	/**
    	 * 返回时间最多的那个
    	 * @param peoples
    	 * @return
    	 */
    	private int getMaxTime(String[] peoples) {
    		// peoples[a，b],根据key找到存在map里面对应的时间，比较2者大小，返回最大时间
    		return Math.max(map.get(peoples[0]), map.get(peoples[1]));
    	}
    
    	/**
    	 * 获取未过桥的所有两两组合的可能组合
    	 * 
    	 * @param listNot
    	 *            未过桥人员列表
    	 * @return
    	 */
    	private List<String> getAllResult(List<String> listNot) {
    		// 把列表类型转换成字符串数组
    		int len = listNot.size();
    		String[] str = new String[len];
    		listNot.toArray(str);
    		int i, j;
    		List<String> result = new ArrayList<>();
    		for (i = 0; i < len - 1; i++) {
    			for (j = 0; j < len; j++) {
    				// 如果组合是【a,a】或者result已经存在组合【a,b】还是【b,a】的情况就不往列表里加数据,其他组合加进列表。
    				if (!str[i].equals(str[j]) && !result.contains(str[i] + COMMA + str[j])
    						&& !result.contains(str[j] + COMMA + str[i])) {
    					result.add(str[i] + COMMA + str[j]);
    				}
    			}
    		}
    		// 组合格式：[A,B , A,C , A,D , B,C , B,D , C,D]
    		return result;
    	}
    
    }

### 效果： ###

第1种情况:
    花费时间--》17
    步骤详情--》
    [C, D]--->{A,B}过桥去了--->[A, B]
    [C, D, A]<---{A}我又返回了<---[B]
    [A]--->{C,D}过桥去了--->[B, C, D]
    [A, B]<---{B}我又返回了<---[C, D]
    []--->{A,B}过桥去了--->[C, D, A, B]
    
    第2种情况:
    花费时间--》17
    步骤详情--》
    [C, D]--->{A,B}过桥去了--->[A, B]
    [C, D, B]<---{B}我又返回了<---[A]
    [B]--->{C,D}过桥去了--->[A, C, D]
    [B, A]<---{A}我又返回了<---[C, D]
    []--->{B,A}过桥去了--->[C, D, B, A]

### 我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。 ###