https://leetcode.cn/problems/open-the-lock/solution/shou-hua-tu-jie-tu-bfs-lin-jie-guan-xi-7-ud8c/
func openLock(deadends []string, target string) int { step := 0 // 旋转次数 deadendsMap := make(map[string]bool) visitedMap := make(map[string]bool) for _, v := range deadends { // 记录所有“死亡点” deadendsMap[v] = true } q := []string{"0000"} // 队列q for len(q) > 0 { // 循环直至队列为空 size := len(q) // 获取BFS当前level的节点个数 for i := 0; i < size; i++ { // 遍历当前层的节点 node := q[0] // 获取出列的节点 q = q[1:] // 节点出列 if node == target { // 如果出列的节点正好是目标节点 return step // 返回当前所用的步数 } if _, ok := visitedMap[node]; ok { // 之前访问过该节点,跳过 continue } if _, ok := deadendsMap[node]; ok { // 遇到“死亡点”,跳过 continue } visitedMap[node] = true // 将该点标记为访问过 for j := 0; j < len(node); j++ { // 通过遍历当前字符串,找出它的所有子节点,安排入列 num := int(node[j] - '0') // 获取当前的数字num up := (num + 1) % 10 // 往上拧所得的新数,比如1变成2 down := (num + 9) % 10 // 往下拧所得的新数,比如7变成6 q = append(q, node[:j]+strconv.Itoa(up)+node[j+1:]) // 拼成新字符串,入列 q = append(q, node[:j]+strconv.Itoa(down)+node[j+1:]) // 拼成新字符串 入列 } } step++ // 当前层的所有节点遍历完毕,层次+1 } return -1 // 无论如何都遇不到目标节点,返回-1 }