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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
第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]