只钟表排成的方阵.pptVIP

The Clocks IOI’94,Day 1,Problem 2 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)的时空内解决。 * * 贾晔 July 5,2003 3 3 0 2 2 2 2 1 2 000 000 000 330 330 000 333 000 000 030 333 030 000 033 033 . . . 223 330 000 323 333 030 . . . 1 2 9 1 5 5 -1 -1 0 0 -1 *