北大poj 1166 The Clocks解题报告源代码
作者：贾晔
The Clocks
9只钟表排成3*3的方阵，每只钟表只能指向上、下、左、右四个位置
9种作用方式，每种使一些钟表的指针右转90°
使用这9种作用，使得所有钟表都指向正上方 (记为状态0)
求使得总作用次数最少的策略
Sample
Input Data
3*3矩阵，元素为0，1，2或3，分别表示钟表指向上，右，下，左
钟表矩阵的有限性
由于矩阵结构及其元素取值范围相当有限，故可能出现的钟表矩阵也是很有限的，即4^9=262144种
由此有限性可以考虑搜索解法
广度优先搜索
从状态0开始搜索
搜索过程：标记可以通过一次作用达到此状态的所有状态为已搜索，然后搜索新标记的状态。搜索过程中保存使用的作用方式
每个状态用一个32位整数的低18位表示,可将结果存在长度为262144的数组中
启发
广度优先搜索的可行意味着作用次数的相当有限
注意到作用的结果与作用的顺序无关，则显然每种作用最多只需使用3次
于是，问题简化为求解同余方程组
同余方程组
把钟表和作用分别从1到9标号，则同余方程组可写为
[C(i) +∑E(i,j) * M (j)] mod 4= 0 (i=1..9)
其中C(i),M(j),E(i,j)分别表示第i个钟表的初始状态，第j种作用的次数，第j种作用是否拨动第i个钟表
写成矩阵的形式
( C + E M ) mod 4 = 0 (*)
我们所求为M的最小非负解M0=M mod 4
显然，当k足够大时，方程
C + E M’ = 4 * k
的解也是 (*) 式的解，故
M0 =M’ mod 4
由于E是与输入无关的系数矩阵，所以我们可以事先求出其逆矩阵E ，则M 可以写成
M =( E ( 4 * k – C ) ) mod 4
这样，我们只需用另一段程序求出E ，问题就可以在O(1)的时空内解决。
评论