package main

// 打开密码锁
func openLock(deadends []string, target string) int {
	deadSet := make(map[string]bool)
	for _, deadend := range deadends {
		deadSet[deadend] = true // 模拟set，即使有重复的，也还是true，相当于set的效果
	}

	q := make([]string, 0)
	visited := make(map[string]bool)
	q = append(q, "0000")
	visited["0000"] = true
	ans := 0
	for len(q) > 0 {
		size := len(q)
		for i := 0; i < size; i++ {
			poll := q[0]
			q = q[1:]
			if poll == target {
				return ans
			}

			if _, ok := deadSet[poll]; ok {
				continue
			}

			for j := 0; j < len(poll); j++ { // 对每个字符，尝试0-9替换
				next := []byte(poll)
				if poll[j] == '0' { // 往小了转
					next[j] = '9'
				} else {
					next[j] = poll[j] - 1
				}

				nextStr := string(next)
				if _, ok := visited[nextStr]; !ok {
					visited[nextStr] = true
					q = append(q, nextStr)
				}

				if poll[j] == '9' {
					next[j] = '0'
				} else {
					next[j] = poll[j] + 1
				}

				nextStr = string(next)
				if _, ok := visited[nextStr]; !ok {
					visited[nextStr] = true
					q = append(q, nextStr)
				}
			}
		}
		ans++
	}

	return -1
}