题目描述：
有一个农夫带一只羊、一筐菜和一只狼过河.
果没有农夫看管，则狼要吃羊，羊要吃菜.
但是船很小，只够农夫带一样东西过河。
问农夫该如何解此难题？
输入：
题目没有任何输入。
输出：
题目可能有种解决方法，求出步骤最少的解决方法，
按顺序输出农夫想把羊、菜、狼全部运过河需要哪几个步骤。
如果需要将羊带过河去则输出“sheep_go”。
如果需要将羊带回来则输出“sheep_come”。
如果需要将菜带过河去则输出“vegetable_go”。
如果需要将菜带回来则输出“vegetable_come”。
如果需要将狼带过河去则输出“wolf_go”。
如果需要将狼带回来则输出“wolf_come”。
如果需要空手返回则输出“nothing_come”。
如果需要空手过河则输出“nothing_go”。
每输出一种方案，输出一行“succeed”。
样例输入：
样例输出：
提示：
题目可能有多组解决方法，每种方法输出后要再空一行。
一种方法中的多句话，每句话占一行。
思路：用广度优先搜索算法
代码如下：
import java.io.FileInputStream;import java.io.BufferedInputStream;import java.io.BufferedOutputStream;import java.io.PrintWriter;import java.io.IOException;import java.util.Queue;import java.util.LinkedList;import java.util.Scanner;import java.util.Arrays;import java.util.Map;import java.util.HashMap;import java.util.List;import java.util.ArrayList;public class Main implements Runnable{private static boolean DEBUG = false;private static final int MAN = 0, WOLF = 1, SHEEP = 2, VEGETABLE = 3, MAX = 4;private static final int SRC = 0, DST = 1;private static Map<Integer, String> roleMap;private static Map<Integer, String> dirMap;private static Scanner cin;private static PrintWriter cout;private Map<Integer, StateNode> map;private class StateNode{int[] state;int parent;public StateNode(){state = new int[MAX];Arrays.fill(state, 0);parent = -1;}}private void init(){try {if (DEBUG){cin = new Scanner(new BufferedInputStream(new FileInputStream("f:\\OJ\\uva_in.txt")));}else{cin = new Scanner(new BufferedInputStream(System.in));}cout = new PrintWriter(new BufferedOutputStream(System.out));roleMap = new HashMap<>();roleMap.put(WOLF, "wolf");roleMap.put(SHEEP, "sheep");roleMap.put(VEGETABLE, "vegetable");dirMap = new HashMap<>();dirMap.put(DST, "go");dirMap.put(SRC, "come");}catch(IOException e){e.printStackTrace();}}private void input(){}private boolean isTarget(StateNode node){if (node.state[MAN] == DST && node.state[WOLF] == DST && node.state[SHEEP] == DST && node.state[VEGETABLE] == DST) return true;return false;}private int hashVal(StateNode node){int ans = 0;for (int i = 0; i < node.state.length; i++){ans |= node.state[i] << i;}return ans;}private boolean isUnpossible(StateNode node){int val = hashVal(node);if (map.containsKey(val)) return true;//人和羊不在一边，而羊和蔬菜在一边if (node.state[SHEEP] == node.state[VEGETABLE] && node.state[MAN] != node.state[SHEEP]) return true;//人和狼不在一边，而狼和羊在一边if (node.state[WOLF] == node.state[SHEEP] && node.state[MAN] != node.state[WOLF]) return true;return false;}private void pre_next_path(StateNode pre, StateNode next){boolean change = false;for (int i = 1; i < MAX; i++){if (pre.state[i] != next.state[i]){cout.print(roleMap.get(i));cout.print("_");cout.print(dirMap.get(next.state[i]));change = true;break;}}if (!change){cout.print("nothing_come");}cout.println();}private StateNode extendCurNode(StateNode node, int pos){StateNode ans = new StateNode();ans.parent = hashVal(node);ans.state[MAN] = 1 - node.state[MAN];if (pos != 0){ans.state[pos] = 1 - node.state[pos];}for (int i = 1; i < MAX; i++){if (i != pos){ans.state[i] = node.state[i];}}return ans;}private void solve(){Queue<StateNode> queue = new LinkedList<>();map = new HashMap<>();StateNode initNode = new StateNode();queue.add(initNode);map.put(hashVal(initNode), initNode);int ans = -1;while (!queue.isEmpty()){StateNode curNode = queue.poll();if (isTarget(curNode)){ans = hashVal(curNode);break;}for (int i = 0; i < MAX; i++){StateNode newNode = null;newNode = extendCurNode(curNode, i);if (isUnpossible(newNode)) continue;queue.add(newNode);map.put(hashVal(newNode), newNode);}}if (ans != -1){List<Integer> path = new ArrayList<>();while (ans != -1){path.add(ans);ans = map.get(ans).parent;}for (int i = path.size() - 2; i >= 0; i--){pre_next_path(map.get(path.get(i + 1)), map.get(path.get(i)));}}cout.flush();}public void run(){init();solve();}public static void main(String[] args){new Thread(new Main()).start();}}
