代码

import java.util.LinkedList; import java.util.List; public class Test2 { /** 可能存在的状态[野人][传教士][方向] */ static int possibilities[][][]; /** 路径 */ static List<State> route = new LinkedList<State>(); static int savageNum = 3; static int preacherNum = 3; static int boatNum = 2; /** * * @param savage 左岸野人数 * @param preacher 左岸传教士数 * @param direction 0：向右岸渡河，1：向左岸渡河 */ public static void move(int savage, int preacher, int direction) { if (savage == 0 && preacher == 0) { System.out.println("--------------------------------------------------------"); for (State state : route) { if (state.direction == 1) { System.out.print("(>【L" + state.preacher + "," + state.savage + "】【B" + state.boatPreacher + "," + state.boatSavage + "】)"); } else { if (state.boatPreacher != 0 || state.boatSavage != 0) { System.out.print("(<【B" + state.boatPreacher + "," + state.boatSavage + "】【R" + (preacherNum - state.preacher) + ", " + (savageNum - state.savage) + "】)"); } } } System.out.println(); return; } // 向右岸渡河 if (direction == 0) { // 渡河野人数量 for (int i = 0; i <= boatNum; i++) // 渡河传教士数量 for (int j = 0; j <= boatNum - i; j++) { // 必须有人渡河 if (i + j >= 1) { // 渡河后，左岸传教士数必须大于野人数 or 传教士人数等于0 if (savage - i <= preacher - j || preacher - j == 0) { // 渡河后，左岸野人数必须大于等于0，同时渡河后不能已经操作过的状态 if (savage - i >= 0 && possibilities[savage - i][preacher - j][1] == -1) { // 船到右岸后，右岸加船上的传教士数必须大于野人数 or 传教士人数等于0 if (savageNum - savage + i <= preacherNum - preacher + j || preacherNum - preacher + j == 0) { possibilities[savage - i][preacher - j][1] = 0; State s = new State(savage - i, preacher - j, 1, i, j); route.add(s); move(savage - i, preacher - j, 1); possibilities[savage - i][preacher - j][1] = -1; route.remove(s); } } } } } } else { // 向右岸渡河后左岸的状态 // 渡河野人数量 for (int i = 0; i <= boatNum; i++) for (int j = 0; j <= boatNum - i; j++) { // 渡河传教士数量 if (i + j >= 1) { // 渡河后，右岸传教士数必须大于野人数 or 传教士人数等于0 if ((savageNum - savage - i) <= (preacherNum - preacher - j) || (preacherNum - preacher - j) == 0) { // 渡河后，左岸传教士不能大于3，同时渡河后不能返回已经操作过的状态 if (savage + i <= savageNum && preacher + j <= preacherNum && possibilities[savage + i][preacher + j][0] == -1) { // 船到左岸后，左岸加船上的传教士数必须大于野人数 or 传教士人数等于0 if (savage + i <= preacher + j || preacher + j == 0) { possibilities[savage + i][preacher + j][0] = 0; State s = new State(savage + i, preacher + j, 0, i, j); route.add(s); move(savage + i, preacher + j, 0); possibilities[savage + i][preacher + j][0] = -1; route.remove(s); } } } } } } return; } public static void main(String[] args) { possibilities = new int[savageNum + 1][preacherNum + 1][2]; for (int i = 0; i <= savageNum; i++) { for (int j = 0; j <= preacherNum; j++) { for (int k = 0; k < 2; k++) { possibilities[i][j][k] = -1; } } } possibilities[savageNum][preacherNum][0] = 0; State s = new State(savageNum, preacherNum, 0, 0, 0); route.add(s); move(savageNum, preacherNum, 0); return; } }

结果

(>【L2,2】【B1,1】)(<【B1,0】【R0, 1】)(>【L3,0】【B0,2】)(<【B0,1】【R0, 2】)(>【L1,1】【B2,0】)(<【B1,1】【R1, 1】)(>【L0,2】【B2,0】)(<【B0,1】【R3, 0】)(>【L0,1】【B0,2】)(<【B1,0】【R2, 2】)(>【L0,0】【B1,1】)

---

(>【L2,2】【B1,1】)(<【B1,0】【R0, 1】)(>【L3,0】【B0,2】)(<【B0,1】【R0, 2】)(>【L1,1】【B2,0】)(<【B1,1】【R1, 1】)(>【L0,2】【B2,0】)(<【B0,1】【R3, 0】)(>【L0,1】【B0,2】)(<【B0,1】【R3, 1】)(>【L0,0】【B0,2】)

---

(>【L3,1】【B0,2】)(<【B0,1】【R0, 1】)(>【L3,0】【B0,2】)(<【B0,1】【R0, 2】)(>【L1,1】【B2,0】)(<【B1,1】【R1, 1】)(>【L0,2】【B2,0】)(<【B0,1】【R3, 0】)(>【L0,1】【B0,2】)(<【B1,0】【R2, 2】)(>【L0,0】【B1,1】)

---

(>【L3,1】【B0,2】)(<【B0,1】【R0, 1】)(>【L3,0】【B0,2】)(<【B0,1】【R0, 2】)(>【L1,1】【B2,0】)(<【B1,1】【R1, 1】)(>【L0,2】【B2,0】)(<【B0,1】【R3, 0】)(>【L0,1】【B0,2】)(<【B0,1】【R3, 1】)(>【L0,0】【B0,2】)

输出结果说明

(>【L2,2】【B1,1】)(<【B1,0】【R0, 1】) >和<表示船行驶方向；（）表示一次渡河；【传教士，野人】表示船离岸时，岸上或船上的传教士野人数量；L表示左岸，B表示船上，R表示右岸 最先有三个传教士，三个野人【3，3】，向右岸（>）行驶的小船上有一个传教士，一个野人【B1，1】 到达右岸后，一个野人上岸【R0,1】,向左岸（<）行驶的小船上有一个传教士【B1,0】