我想要一个O(1)方法来检查我是否处于某种状态。问题在于状态是由地图上几个缩放比例的位置定义的。 Zoombini = {(1,1):0,(2,2):1,(3,3):3} {Position:Zoombini ID} 我正在使用广度优先搜索,并推送到我的队列此字典的职位。词典是一个字典中的关键Python
dirs = [goNorth, goSouth, goWest, goEast] ## List of functions
zoom = {}
boulders = {}
visited = {} ## {(zoom{}): [{0,1,2},{int}]}
## {Map: [color, distance] 0 = white, 1 = gray, 2 = black
n = len(abyss)
for i in xrange(n):
for j in xrange(n):
if (abyss[i][j] == 'X'):
boulders[(i,j)] = True
elif (isInt(abyss[i][j])):
zoom[(i,j)] = int(abyss[i][j]) ## invariant only 1 zomb can have this position
elif (abyss[i][j] == '*'):
exit = (i, j)
sQueue = Queue.Queue()
zombnum = 0
done = False
distance = 0
sQueue.put(zoom)
while not(sQueue.empty()):
currZomMap = sQueue.get()
for zom in currZomMap.iterkeys(): ## zoom {(i,j): 0}
if not(zom == exit):
z = currZomMap[zom]
for fx in dirs: ## list of functions that returns resulting coordinate of going in some direction
newPos = fx(zom)
newZomMap = currZomMap.copy()
del(newZomMap[zom]) ## Delete the old position
newZomMap[newPos] = z ## Insert new Position
if not(visited.has_key(newZomMap)):
sQueue.put(newZomMap)
我的实现没有完成,但我需要一个更好的方法来检查我是否已经访问过一个状态。我可以创建一个函数来创建字典中的整数哈希,但我不认为我能够有效。时间也是一个问题。我怎样才能做到这一点最佳?
如果你发布了一些关于**的代码,这将是一个有效的答案。 **你做了这个散列函数。如果你正在写这个“答案”来简单地否定你原来的帖子,那么你应该删除它,而不是 – inspectorG4dget
刚刚编辑它。 – Nonconformist
你的'x'和'y'值总是在0到9之间吗?如果不是,你的散列有很多冲突,如{{(100,0):0},{{0,10}:0}和{{(0,0):1}到'100'。对于较大的字典,哈希值也取决于您在字典的键上进行迭代的顺序,在添加和删除内容时不能保证稳定。 – Blckknght