状态机
# 野人与传教士渡河
两岸的野人数<=传教士人数；
必须有人驾船；
public class Cross {
static class State{
int y;
int c;
int dir;
int by;
int bc;
public State(int y, int c, int dir, int by, int bc) {
this.y = y;
this.c = c;
this.dir = dir;
this.by = by;
this.bc = bc;
}
}
static List<State> route = new LinkedList<>();
static int yNum;
static int cNum;
static int boatNum;
static boolean[][][] vis;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
yNum = sc.nextInt();
cNum = sc.nextInt();
boatNum = sc.nextInt();
vis = new boolean[yNum+1][cNum+1][2]; // 左岸野人，左岸传教士，方向 0向右 1向左
vis[yNum][cNum][0] = true;
State s = new State(yNum,cNum,0,0,0);
route.add(s);
move(yNum,cNum,0);
}
// 左岸野人，左岸传教士，方向
public static void move(int y,int c,int dir){
if(y==0 && c==0){
System.out.println("===================================");
for(State state:route){
if(state.dir==1){
System.out.println("左岸的传教士："+state.c+" 野人："+state.y+" 船上的传教士："+state.bc+" 野人："+state.by);
}else{
if(state.bc!=0 || state.by!=0){
System.out.println("船上的传教士："+state.bc+" 野人："+state.by+" 右岸的传教士："+(cNum-state.c)+" 野人：" + (yNum-state.y));
}
}
}
System.out.println();
return ;
}
// 向右岸渡河
if(dir==0){
// 渡河野人数量
for(int i=0;i<=boatNum;i++){
// 渡河传教士数量
for(int j=0;j<=boatNum-i;j++){
// 船上必须有人
if(i+j>=1){
// 渡河后，左岸传教士>=野人 ， 或传教士为0
if(y-i <= c-j || c-j==0){
// 渡河后，当左岸野人数>=0
if(y-i>=0 && !vis[y-i][c-j][1]){
// 船到右岸后，右岸加船上的传教士数>=野人数 或 传教士=0
if(yNum-y+i <= cNum-c+j || cNum-c+j==0){
vis[y-i][c-j][1] = true;
State s = new State(y-i,c-j,1,i,j);
route.add(s);
move(y-i,c-j,1);
vis[y-i][c-j][1] = false;
route.remove(s);
}
}
}
}
}
}
}else{
for(int i=0;i<=boatNum;i++){
for(int j=0;j<=boatNum-i;j++){
if(i+j>=1){
// 渡河后，右岸传教士 >= 野人数 或 传教士为0
if(yNum-y-i <= cNum-c-j || cNum-c-j==0){
// 渡河后，左岸传教士和野人不能超过最大值
if(y+i<=yNum && c+j<=cNum && !vis[y+i][c+j][0]){
// 船到左岸后，左岸加船上的传教士>野人数 或 传教士为0
if(y+i<=c+j || c+j==0){
vis[y+i][c+j][0] = true;
State s = new State(y+i,c+j,0,i,j);
route.add(s);
move(y+i,c+j,0);
vis[y+i][c+j][0] = false;
route.remove(s);
}
}
}
}
}
}
}
}
}
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
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
# 365. 水壶问题 (opens new window)
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
// 特判
if (z == 0) {
return true;
}
if (x + y < z) {
return false;
}
State initState = new State(0, 0);
// 广度优先遍历使用队列
Queue<State> queue = new LinkedList<>();
Set<State> visited = new HashSet<>();
queue.offer(initState);
visited.add(initState);
while (!queue.isEmpty()) {
State head = queue.poll();
int curX = head.getX();
int curY = head.getY();
// curX + curY == z 比较容易忽略
if (curX == z || curY == z || curX + curY == z) {
return true;
}
// 从当前状态获得所有可能的下一步的状态
List<State> nextStates = getNxtState(curX, curY, x, y);
// 打开以便于观察，调试代码
// System.out.println(head + " => " + nextStates);
for (State nextState : nextStates) {
if (!visited.contains(nextState)) {
queue.offer(nextState);
// 添加到队列以后，必须马上设置为已经访问，否则会出现死循环
visited.add(nextState);
}
}
}
return false;
}
List<State> getNxtState(int curX,int curY,int x,int y){
List<State> list = new ArrayList<>(8);
State s1 = new State(x,curY); // 将x加满
State s2 = new State(curX,y); // 将y加满
State s3 = new State(0,curY); // 将x清空
State s4 = new State(curX,0); // 将y清空
State s5 = new State(curX-(y-curY),y); // X倒满Y，X还有剩
State s6 = new State(0,curX+curY); // X倒给Y，X没剩
State s7 = new State(x,curY-(x-curX)); // Y倒满X，Y还有剩
State s8 = new State(curX+curY,0); // Y倒给X，Y没剩
// 没有满才需要倒水
if(curX<x)
list.add(s1);
if(curY<y)
list.add(s2);
// 有水才能清空
if(curX>0)
list.add(s3);
if(curY>0)
list.add(s4);
// 有剩余才倒
if(curX-(y-curY)>0)
list.add(s5);
if(curY-(x-curX)>0)
list.add(s7);
// 倒过去倒不满
if(curX+curY<y)
list.add(s6);
if(curX+curY<x)
list.add(s8);
return list;
}
class State{
int x;
int y;
public State(int x,int y){
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
}
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
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