考虑一个由正方形单元格组成的W × H矩形,每个单元格的面积为1。 每个单元格以概率为0.5独立地涂成黑色,否则为白色。 假设共享一个边缘的黑色单元已连接。 考虑连接单元的最大面积。 定义E(W,H)为该最大面积的期望值。 例如, E(2,2) = 1.875,如下图所示。

2x2
已知E(4,4) = 5.76487732,四舍五入到小数点后8位。
求E(7,7),四舍五入到小数点后8位。

画图程序:

n=3
m=2
def e(n,m):
 g=2**(n*m)
 ch='□■'
 for i in range(0,g):
  print("area",i)
  s=bin(i+g)[3:]
  x=0
  for j in s:
   x+=1
   print(ch[int(j)],end='')
   if x==n:print('');x=0    

使用并查集实现的算法,算4x4要5秒

class UnionFind(object):
    """并查集类"""
    def __init__(self, n):
        """长度为n的并查集"""
        self.uf = [-1 for i in range(n + 1)]    # 列表0位置空出
        self.area = [1 for i in range(n + 1)]    #某个根的集合面积 列表0位置空出
        self.sets_count = n                     # 判断并查集里共有几个集合, 初始化默认互相独立
        self.s=[]
    def find2(self, p):
        """查找p的根结点(祖先)"""
        r = p
        while self.uf[p] > 0:
            p = self.uf[p]
        while r != p:
            self.uf[r], r = p, self.uf[r]
        return p
    def find(self, p):
        """尾递归"""
        if self.uf[p] < 0:
            return p
        self.uf[p] = self.find(self.uf[p])
        return self.uf[p]
    def union(self, p, q):
        """连通p,q 让q指向p"""
        proot = self.find(p)
        qroot = self.find(q)
        if proot == qroot:
            return
        elif self.uf[proot] > self.uf[qroot]:   # 负数比较, 左边规模更小
            self.area[qroot]+=self.area[proot]
            self.uf[qroot] += self.uf[proot]
            self.uf[proot] = qroot
        else:
            self.uf[proot] += self.uf[qroot]  # 规模相加
            self.area[proot]+=self.area[qroot] 
            self.uf[qroot] = proot

        self.sets_count -= 1                    # 连通后集合总数减一
    def is_connected(self, p, q):
        """判断pq是否已经连通"""
        return self.find(p) == self.find(q)     # 即判断两个结点是否是属于同一个祖先

def setcolor(w,h):
  totalarea=0
  g=2**(w*h)
  ch='□■'
  color=[0]*(w*h+1)
  for  i  in  range(0,g):  #遍历每种图案
    b=bin(i+g)[3:]
    x=0
    x1=0
    for  j  in  b:
      x+=1
      x1+=1
      color[x]=j    #按二进制数填充当前颜色
      #print(ch[int(j)],end='')
      #if  x1==w:print('');x1=0  
    uf=UnionFind(w*h)  #并查集对象
    #uf.js(w,h)
    #print(i,uf.s)
    for  j  in  range(1,w*h+1):
      #把每格分配到集合,然后取area最大的值
      #if  color[j]=='1':uf.add(j,color)
      if color[j]=='1' and (j-1)%w>0 and j-1>0 and not uf.is_connected(j,j-1) and color[j]==color[j-1]: uf.union( j,j-1) 
      if color[j]=='1' and j-w>0 and not uf.is_connected(j,j-w) and color[j]==color[j-w]: uf.union( j,j-w)     #颜色相同的相邻格加入同一个集合
    #print(i,"==>",color,  end='  ')
    maxarea=0
    for  j  in  range(1,w*h+1):
      if  color[j]=='1'  and  uf.area[j]>maxarea:  maxarea=uf.area[j]
    totalarea+=maxarea
    #print(i,"==>",maxarea,uf.area,uf.uf,'\n')
  return  totalarea/g


w,h=4,4


import time
tm=time.time()
print(setcolor(w,h),time.time()-tm)

5.7648773193359375 4.237565040588379