用两个五位二进制数top和bottom分别表示顶部和底部行种子的状态，1表示有种子，2表示无种子。
用x,y分别表示蚂蚁的横纵坐标，用seed标识其是否携带种子，1表示携带种子，2表示未携带种子。
如此则可以用一个五元组(top,bottom,x,y,seed)来描述当前局面，状态总数是$25\binom{11}{5}=11550$。
接下来使用广度优先搜索，每一步可以到达的状态及其概率可以用一个对应的字典来描述，其中初始状态是(0,31,2,2,0)，概率是1。
每次搜索时遍历当前字典，若是某个状态是最终状态（top=31），就将步数×该状态的概率添加到结果中，否则遍历其邻居，按规则更新状态和概率放到下一步的字典中。
根据实际运行的情况，只需考察前2500步就可得结果$430.088247$。
注：为便于浮点数除法计算，以下为Python 3代码。
neiboursMap={
(0,0):[(1,0),(0,1)],
(4,0):[(3,0),(4,1)],
(0,4):[(0,3),(1,4)],
(4,4):[(3,4),(4,3)],
(1,0):[(0,0),(2,0),(1,1)],
(2,0):[(1,0),(3,0),(2,1)],
(3,0):[(2,0),(4,0),(3,1)],
(1,4):[(0,4),(2,4),(1,3)],
(2,4):[(1,4),(3,4),(2,3)],
(3,4):[(2,4),(4,4),(3,3)],
(0,1):[(0,0),(0,2),(1,1)],
(0,2):[(0,1),(0,3),(1,2)],
(0,3):[(0,2),(0,4),(1,3)],
(4,1):[(4,0),(4,2),(3,1)],
(4,2):[(4,1),(4,3),(3,2)],
(4,3):[(4,2),(4,4),(3,3)],
}
q={(0,31,2,2,0):1}
r=k=0
while k < 2500:
q2={}
for status in q:
top,bottom,x,y,seed=status
if top==31:
r+=k*q[status]
else:
neibours=neiboursMap.get((x,y),[(x-1,y),(x+1,y),(x,y-1),(x,y+1)])
m=len(neibours)
for a,b in neibours:
top2,bottom2,seed2=top,bottom,seed
if b==4 and seed==1 and not (top&(1<<a)):
top2=top2|(1<<a)
seed2=0
if b==0 and seed==0 and (bottom&(1<<a)):
bottom2=bottom2^(1<<a)
seed2=1
status2=(top2,bottom2,a,b,seed2)
q2[status2]=q2.get(status2,0)+q[status]/m
k+=1
q=q2
if k%25==0:print(f"{k//25} percent completed, current r: {r:.6f}")
print(f"{r:.6f}")
|
