IBM Ponder This #274 · 2021 年 2 月

N×N 网格坐标为 1 至 N，每人只在自己信任的邻居全部接种后才接种；没有可信邻居的人自动接种。直接说服一个初始人群，可以引发后续连锁反应。求使最终全员接种的最小启动集合。

每格用四位比特表示是否信任上、右、下、左邻居，1 为信任；网格外的邻居不计。用一位十六进制数压缩这四位。例如 (2,3) 的 1001 表示信任 (2,4) 与 (1,3)；角点 (1,N) 的 1111 等价于 0110。

以下 3×3 示例中，直接说服 (1,2) 即足够：

 381
 79c
 26c

它依赖右邻 (2,2) 与下邻 (1,1)，后者没有实际可信邻居而自动接种。

任务：求下面 12×12 网格的最小启动集合：

 0a8301b11b01
 1bda41b24d78
 37c09e8d5998
 60473283d3b8
 13279043d9bc
 371bf4c021c1
 1d122e800ee1
 5bc967265d88
 5f1998f5915d
 628dff094034
 39effbe6ecc8
 2c440c20e0a0

附加问题：构造一个 12×12 网格，使最小启动集合恰好有 42 人。

解答

认真尝试后再打开

待补充。