我想要一个 O(1) 方法来检查我是否处于某种状态。问题在于,一个状态是由地图上几个 zoombinis 的位置定义的。Zoombini = {(1,1): 0, (2,2):1, (3,3):3} {Position: Zoombini ID} 我正在使用广度优先搜索并将这个位置字典推送到我的队列中.
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)
我的实现尚未完成,但我需要一种更好的方法来检查我是否已经访问过一个状态。我可以创建一个从字典中创建整数散列的函数,但我认为我不能有效地做到这一点。时间也是一个问题。我怎样才能以最佳方式解决这个问题?