没想到，像我这样傻的人也接触算法了！ 还好，只是最简单的算法。

前言

开始之前，我要吐槽下当时的算法课。学到图的遍历，老师就给我们把BFS和DFS的流程讲了一遍，然后对于应用，内涵一笔带过。 （淡然，可能是我开小差，然后，就没听到。。。。） 今天在刷leetcode的时候，做到了Open the Lock的题目，我第一眼看上去是头晕的，看不明白什么含义。 看完别人的讨论才明白可以用广度优先搜索来做。

题目

题目就是有一个双向环，从0-9可以互相转换，然后给一个目标值，比如1234，求最快的办法可以使0000转换过去。 当然，得有一些附加条件，比如一次只能改变一位，以及不能转换过程中经过一些特定序列。 这个题目内容是经过我魔幻翻译的结果。具体的可以去看官网的描述。

BFS算法

我找一个起点，找它所有有联系的节点，然后再从它有联系的节点开始，继续找有联系的节点。就是广撒网嘛，不是瞅准一个方向死磕到底，而是相当于一层一层的往后面看。 大体流程就是

1
2
3
4
5
6
7
8

队列初始化Q
Q={起点S};S已访问
while(Q非空){
	取Q队首元素f;f出队
	if(u==目标状态){...}
	与u相邻且未被访问的点进入队列
	标记u为已访问
}

解决

可以解决问题了，从0000开始，找0000能够转换的所有值，比如[1000 9000 0100 0900 0010 0090 0001 0009]，然后再从这8个开始广撒网，看看能不能遇到正确的，不对的话，继续下一层，直到找到。 当然了，我们这些查看过的值都得标记下，已经访问了，要不然下次还访问一遍，效率没保证，能不能解决问题都不一定了。 还有了，我们有特定序列不能转换的，我们在往队列里面放的时候得确定不是特定序列里面的，要不然就会出错了。 整体代码如下

 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

import (
	"container/list"
	"fmt"
	"time"
)

// https://leetcode.com/problems/open-the-lock/description/

func main() {
	deadends := []string{"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"}
	target := "8888"
	t := time.Now()
	dis := openLock(deadends, target)
	fmt.Println(dis)
	fmt.Println(time.Now().Sub(t))
}

func openLock(deadends []string, target string) int {

	deadendsMap := make(map[string]int)
	for _, str := range deadends {
		deadendsMap[str] = 1
	}

	if contains(deadendsMap, "0000") || contains(deadendsMap, target) {
		return -1
	}
	if target == "0000" {
		return 0
	}
	q := list.New()
	q.PushBack("0000")
	v := make(map[string]int)
	for d := 1; q.Len() != 0; d++ {
		for n := q.Len(); n > 0; n-- {
			s := q.Front()
			for i := 0; i < 4; i++ {
				for j := 1; j <= 9; j += 8 {
					str := []byte(s.Value.(string))
					str[i] = (str[i]+uint8(j)-'0')%10 + '0'
					if string(str) == target {
						return d
					}
					if !contains(deadendsMap, string(str)) && ! contains(v,string(str)){
						q.PushBack(string(str))
					}
					v[string(str)] = 0
				}
			}
			q.Remove(s)
		}

	}
	return -1
}

func contains(source map[string]int, target string) bool {
	_, ok := source[target]
	if ok {
		return true
	}
	return false
}

为什么我用了map呢？value似乎就是随便设置的样子？ 因为go的list没有contains的操作，我自己遍历非常慢，那就用go内建的map来查找吧。

参考文档: 1.BFS和DFS算法原理（通俗易懂版）