← 完整题目索引

PROJECT EULER · #0331

交叉翻转

Cross Flips

仅题目 · 待解原题 ↗

N×N 个圆盘放置在方形游戏板上。每个圆盘都有黑面和白面。

每回合,你可以选择一个圆盘,并翻转与该圆盘同一行、同一列的所有圆盘:这样就翻转了 2×N1 个圆盘。当所有圆盘都露出白色面时游戏结束。以下示例显示了 5×5 棋盘上的游戏。

0331_crossflips3.gif

可以证明3是完成这个游戏的最少回合数。

N×N 棋盘上左下角的圆盘坐标为 (0,0)
右下圆盘的坐标为 (N1,0),左上圆盘的坐标为 (0,N1)

CN 为具有 N×N 磁盘的主板的以下配置:
位于 (x,y) 的圆盘满足 N1x2+y2<N,显示其黑色面;否则,它会显示其白色的一面。 C5 如上所示。

T(N) 为从配置 CN 开始完成游戏的最小回合数,如果配置 CN 无法解决,则为 0
我们已经证明T(5)=3。您还可以得到 T(10)=29T(1000)=395253

i=331T(2ii)

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。