解题思路
记网格总格子数为 N=n×m。初始时,每个格子为激活态(R)或未激活态(W)。首先找出所有初始的激活连通片,统计其数量 C0。
操作方式为:等概率随机选择一个格子,将其变为激活态。若选中的格子原本就是激活态,则连通片数量不变;若选中的是未激活态格子,则将其变为激活态后,连通片数量会发生变化。
对于一个未激活的白格,观察其上下左右四个方向相邻的格子:
- 若四周没有激活态格子(k=0),则它会单独形成一个新的激活连通片,总连通片数增加 1,相当于变化量 +1;
- 若四周接触到的激活态格子分别属于 k 个不同的激活连通片,将该白格变为激活态后,这 k 个连通片以及这个新格子会合并成 1 个连通片,因此总连通片数减少 k−1,变化量为 1−k。