Project Euler第11题扩展：n个连通相邻数的最大乘积与形状计数公式问询

自动生成所有n个连通相邻数组合的方法 #

• 递归生长+标准化去重：从单个单元格出发，每次向上下左右（若允许斜向则包含对角线）的未占用单元格扩展，直到组合大小达到n。为避免重复生成相同形状，需要对每个生成的形状做标准化处理——比如将所有单元格的坐标平移，让形状的左上角对齐到原点，或者按固定顺序（如先行后列）排序单元格坐标，再将标准化后的形状存入集合去重。
• 动态规划逐步构建：基于已生成的k个单元格的连通形状，向每个形状的所有相邻空白单元格扩展，得到k+1个单元格的形状，同样通过标准化去重后保留。这种方法可以从n=1逐步迭代到目标n，复用之前的计算结果，减少冗余。
• 连通子图枚举：把网格单元格视为图的节点，相邻单元格间连边，问题转化为枚举所有含n个节点的连通子图。可以用深度优先搜索（DFS）遍历所有可能的子图，配合标准化步骤过滤重复项。

连通形状数量的计算 #

这类连通形状属于多格骨牌（Polyominoes），目前没有简洁的闭合公式能直接计算其数量，只能通过枚举或递推得到：

• 多格骨牌的定义就是n个正方形边对边连接形成的连通图形，完全匹配你的需求。
• 已通过计算机计算得到的部分n对应的数量：
  • n=1：1
  • n=2：1
  • n=3：2
  • n=4：5
  • n=5：12
  • n=6：35
  • n=7：108
• 随着n增大，数量呈指数级增长，计算复杂度急剧上升，目前只能依靠高效的计算机算法来枚举或递推。

内容的提问来源于stack exchange，提问作者KungFuPanda