怎么用一个容量为 3 公斤的桶和一个容量 5 公斤的桶称量出 4 公斤量的水？

  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

package main

import "fmt"

// State 状态，构成图的顶点
type State struct {
	// A、B 两桶当前装水的容量
	a, b int

	// 遍历时记录父顶点，即记住路径
	parent *State

	// 所作的动作
	action string
}

const (
	// M 为 A 桶的最大容量
	M = 3
	// N 为 B 桶的最大容量
	N = 5
	// G 为想要得到的容量
	G = 4
)

const (
	actionFillA      = `Fill A`
	actionFillB      = `Fill B`
	actionClearA     = `Clear A`
	actionClearB     = `Clear B`
	actionFillAWithB = `Fill A With B`
	actionFillBWithA = `Fill B With A`
)

var (
	// A 桶的范围是 [0,M]，B 桶的范围是 [0,N]
	// 所以去重后的状态总数是 (M+1)*(N+1)
	maxStates = (M + 1) * (N + 1)

	// 状态集合。
	states = make([]*State, 0, maxStates)

	// 已访问的状态。
	// 这里用一维数组，方便初始化
	visited = make([]bool, maxStates)
)

// 把未访问过的状态加入到待遍历队列
func tryAddState(a, b int, parent *State, action string) {
	p := (N+1)*a + b
	if visited[p] {
		return
	}

	states = append(states, &State{
		a:      a,
		b:      b,
		parent: parent,
		action: action,
	})

	visited[p] = true
}

// 到达结束状态时递归回溯并显示出路径
func backtrace(s *State) {
	if s != nil {
		backtrace(s.parent)
		fmt.Printf("(%d,%d) %s\n", s.a, s.b, s.action)
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	// 加入开始状态，准备广度优先搜索遍历
	tryAddState(0, 0, nil, `Initialize`)

	// 遍历所有状态（不要使用 range，因为 range 是立即求值）
	for i := 0; i < len(states); i++ {
		s := states[i]

		// 如果到达结束条件
		if s.a == G || s.b == G {
			// 回溯并输出当前路径
			backtrace(s)
			fmt.Println()
			continue
		}

		// 如果没达到结束条件，把当前顶点的所有出度加入列表

		tryAddState(0, s.b, s, actionClearA)
		tryAddState(s.a, 0, s, actionClearB)
		tryAddState(M, s.b, s, actionFillA)
		tryAddState(s.a, N, s, actionFillB)

		// A 最多可以给 B 的量
		t1 := min(s.a, N-s.b)
		// B 最多可以给 A 的量
		t2 := min(s.b, M-s.a)

		tryAddState(s.a+t2, s.b-t2, s, actionFillAWithB)
		tryAddState(s.a-t1, s.b+t1, s, actionFillBWithA)
	}

	fmt.Printf("Processed %d states\n", len(states))
}