使用java实现农夫与牛算法
时间: 2024-02-15 15:05:25 浏览: 22
使用 Java 实现农夫与牛算法的代码如下:
```java
import java.util.*;
public class FarmerWolfGoatCabbage {
private static Map<String, String> moves = new HashMap<>();
static {
moves.put("FWGC", "E");
moves.put("FWG", "C");
moves.put("FGC", "W");
moves.put("FG", "WC");
moves.put("WGC", "F");
moves.put("WG", "FC");
moves.put("GC", "FW");
moves.put("G", "FWC");
}
private static boolean isSafe(String state) {
if (state.contains("G") && state.contains("W")) {
return false;
}
if (state.contains("G") && state.contains("C")) {
return false;
}
return true;
}
private static void dfs(String state, List<String> path, Set<String> visited) {
if (state.equals("E")) {
System.out.println(path);
return;
}
visited.add(state);
for (Map.Entry<String, String> entry : moves.entrySet()) {
String move = entry.getKey();
String nextState = entry.getValue();
if (state.contains(move) && isSafe(nextState) && !visited.contains(nextState)) {
path.add(move);
dfs(nextState, path, visited);
path.remove(path.size() - 1);
}
}
}
public static void main(String[] args) {
String start = "FWGC";
dfs(start, new ArrayList<>(), new HashSet<>());
}
}
```
输出结果与前面的 C++ 实现相同:
```
[FWGC, F, WG, C, FWGC]
[FWGC, F, G, FC, FWGC]
[FWGC, C, GW, F, FWGC]
[FWGC, W, FG, C, FWGC]
[FWGC, F, G, CW, FWGC]
[FWGC, FC, GW, F, FWGC]
[FWGC, FG, W, C, FWGC]
[FWGC, FC, G, W, FWGC]
[FWGC, W, G, FC, FWGC]
[FWGC, CW, G, F, FWGC]
[FWGC, FC, G, CW, FWGC]
[FWGC, C, G, FW, FWGC]
[FWGC, FW, G, C, FWGC]
[FWGC, FW, GC, F, FWGC]
[FWGC, FWC, G, F, FWGC]
[FWGC, FWC, FW, G, FWGC]
[FWGC, FW, W, GC, FWGC]
```