照着别人写了如下程序, 不理解为什么steps 最后只加到了6. 为什么不是每进一个newstr 就加一次呢?
当然6是我想要的结果,因为想得到到最终结果的距离。 求大神解析! 谢谢
import collections
class Solution:
def openLock(self, deadends, target):
start = '0000'
queue = collections.deque([(start,0)])
seen = set(start)
#print(seen)
dead_set = set(deadends)
count = 0
if target == start: # if target is same as start, return -1
return -1
while queue:
#print(len(queue))
(testNum,steps) = queue.popleft()
#print(steps)
if testNum == target:
#print(queue)
return steps
elif testNum in dead_set:
continue
#if testNum in seen:
#continue
#print(testNum)
for i in range(len(testNum)):
for j in range(-1,2):
sum_num = (int(testNum[i])+j+10)%10
newstr = testNum[:i] + str(sum_num)+ testNum[i+1:]
#newstr = str("%4d"%newnum).replace(' ','0')
if newstr not in seen:
queue.append((newstr, steps+1 ))
seen.add(newstr)
print(queue)
solution1 = Solution()
deadends = ["0201","0101","0102","1212","2002"]
target = "0202"
print(solution1.openLock(deadends, target))
当然6是我想要的结果,因为想得到到最终结果的距离。 求大神解析! 谢谢
import collections
class Solution:
def openLock(self, deadends, target):
start = '0000'
queue = collections.deque([(start,0)])
seen = set(start)
#print(seen)
dead_set = set(deadends)
count = 0
if target == start: # if target is same as start, return -1
return -1
while queue:
#print(len(queue))
(testNum,steps) = queue.popleft()
#print(steps)
if testNum == target:
#print(queue)
return steps
elif testNum in dead_set:
continue
#if testNum in seen:
#continue
#print(testNum)
for i in range(len(testNum)):
for j in range(-1,2):
sum_num = (int(testNum[i])+j+10)%10
newstr = testNum[:i] + str(sum_num)+ testNum[i+1:]
#newstr = str("%4d"%newnum).replace(' ','0')
if newstr not in seen:
queue.append((newstr, steps+1 ))
seen.add(newstr)
print(queue)
solution1 = Solution()
deadends = ["0201","0101","0102","1212","2002"]
target = "0202"
print(solution1.openLock(deadends, target))

