...
https://leetcode.com/problems/open-the-lock/
| Code Block | ||
|---|---|---|
| ||
import "fmt" func openLock(deadends []string, target string) int { var q []string visited := make(map[string]bool) for _, x := range deadends { visited[x] = true } if visited["0000"] { return -1 } q = append(q, "0000") visited["0000"] = true step := 0 for len(q) > 0 { qq := q q = nil for _, node := range qq { if node == target { return step } for _, next := range getNext(node) { if visited[next] { continue } q = append(q, next) visited[next] = true } } step++ } return -1 } func getNext(node string) []string { result := make([]string, 0, 8) nb := []byte(node) add := func(i, x int) { v := (int(nb[i] - '0') + x + 10) % 10 nb[i] = '0' + byte(v) } for i := 0; i < 4; i++ { add(i, 1) result = append(result, string(nb)) add(i, -2) result = append(result, string(nb)) add(i, 1) } return result } |
优化：双向 BFS
头尾同时遍历（实际代码上是遍历一端完再遍历另一端），出现交集时返回
| Code Block | ||
|---|---|---|
| ||
func openLock(deadends []string, target string) int { visited := make(map[string]bool) for _, x := range deadends { visited[x] = true } if visited["0000"] { return -1 } q1 := make(map[string]bool) q2 := make(map[string]bool) q1["0000"] = true q2[target] = true step := 0 for len(q1) > 0 && len(q2) > 0 { temp := make(map[string]bool) for node := range q1 { if q2[node] { return step } visited[node] = true for _, next := range getNext(node) { if visited[next] { continue } temp[next] = true } } step++ q1, q2 = q2, temp } return -1 } func getNext(node string) []string { result := make([]string, 0, 8) nb := []byte(node) add := func(i, x int) { v := (int(nb[i] - '0') + x + 10) % 10 nb[i] = '0' + byte(v) } for i := 0; i < 4; i++ { add(i, 1) result = append(result, string(nb)) add(i, -2) result = append(result, string(nb)) add(i, 1) } return result } |