本题除了枚举+回溯以外似乎也没什么好方法。
考虑一个$30\times 30$的格子，前两格位于中间且呈固定的方向，记录当前串的长度、串尾坐标以及串中的成分的接触情况（用位或运算表示第i位和第j位接触）。
使用深度优先搜索尝试填入格子并回溯以得到所有可能的序列接触情况。
最后，再次枚举序列并统计对应的接触数，最终结果是$8.0540771484375$。
注：为便于作除法，以下为Python 3代码。
def tryOut(t,u,v,s):
for x,y in [(u-1,v),(u+1,v),(u,v-1),(u,v+1)]:
if b[x][y]!=-1:
s|=1 << g[t-1][b[x][y]]
if t==target:
p.add(s)
else:
for x,y in [(u-1,v),(u+1,v),(u,v-1),(u,v+1)]:
if b[x][y]==-1:
b[x][y]=t
tryOut(t+1,x,y,s)
b[x][y]=-1
target=15
g=[[-1]*target for i in range(target)]
b=[[-1]*(target*2+1) for i in range(target*2+1)]
rp=[0]*(1 << target)
mx=[0]*(1 << target)
p=set()
m=0
for i in range(0,target,2):
for j in range(1,target,2):
g[i][j]=g[j][i]=m
m+=1
b[target][target]=0
b[target][target+1]=1
tryOut(2,target,target+1,g[0][1])
q=[]
for s in sorted(p,reverse=True):
i=0
while q and i < len(q) and q[i]|s!=q[i]:
i+=1
if i==len(q):
q.append(s)
res=0
for s in range(1 << target):
rp[s]=((rp[s//2]//2))|((s%2) << (target-1))
if rp[s] < s:
res+=mx[rp[s]]
else:
y=0
for i in range(0,target,2):
for j in range(1,target,2):
if (s>>i)%2==(s>>j)%2==1:
y|=1 << g[i][j]
for x in p:
mx[s]=max(mx[s],format(x&y,"b").count('1'))
res+=mx[s]
print(res/(1 << target))
|
