forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathopen-the-lock.py
More file actions
70 lines (62 loc) · 2.34 KB
/
open-the-lock.py
File metadata and controls
70 lines (62 loc) · 2.34 KB
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
"""
In priority queue, we not only take `steps` in to consideration but also `distance`
And the rest is just like dijkstra.
"""
import heapq
class Solution(object):
def openLock(self, deadends, target):
def getNeighbor(node):
opt = []
for i in xrange(len(node)):
if node[i]==0:
opt.append(tuple(node[:i]+(1,)+node[i+1:]))
opt.append(tuple(node[:i]+(9,)+node[i+1:]))
elif node[i]==9:
opt.append(tuple(node[:i]+(0,)+node[i+1:]))
opt.append(tuple(node[:i]+(8,)+node[i+1:]))
else:
opt.append(tuple(node[:i]+(node[i]+1,)+node[i+1:]))
opt.append(tuple(node[:i]+(node[i]-1,)+node[i+1:]))
return opt
def getDistance(node):
distance = 0
for i in xrange(len(node)):
d = abs(int(node[i])-int(target[i]))
d2 = abs(10-d)
distance+=min(d, d2)
return distance
def tupify(node):
return tuple(map(int, node))
target = tupify(target)
visited = set([tupify(node) for node in deadends])
pq = [(0, 0, tupify('0000'))]
while pq:
_, steps, node = heapq.heappop(pq)
if node==target: return steps
if node in visited: continue
visited.add(node)
for nei in getNeighbor(node):
heapq.heappush(pq, (steps+1+getDistance(nei), steps+1, nei))
return -1
class Solution:
def openLock(self, deadends, target):
def getNeighbor(node):
opt = []
for i in xrange(len(node)):
add_one = delta[node[i]][0]
minus_one = delta[node[i]][1]
opt.append(node[:i]+add_one+node[i+1:])
opt.append(node[:i]+minus_one+node[i + 1:])
return opt
delta = {str(i): [str((i+1)%10), str((i-1)%10)] for i in xrange(10)}
visited = set(deadends)
q = collections.deque([('0000', 0)])
steps = 0
while q:
node, steps = q.popleft()
if node==target: return steps
if node in visited: continue
visited.add(node)
for nei in getNeighbor(node):
q.append((nei, steps+1))
return -1