北大poj 1166 The Clocks解题报告源代码 作者：贾晔 The Clocks 9只钟表排成3*3的方阵，每只钟表只能指向上、下、左、右四个位置9种作用方式，每种使一些钟表的指针右转90°使用这9种作用，使得所有钟表都指向正上方 (记为状态0)求使得总作用次数最少的策略 Sample   Input Data3*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)的时空内解决。   http://www.608088.com/show-57-1.html

评论