只钟表排成的方阵.ppt

《只钟表排成的方阵.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、TheClocksIOI’94,Day1,Problem2贾晔July5,2003TheClocks9只钟表排成3*3的方阵，每只钟表只能指向上、下、左、右四个位置9种作用方式，每种使一些钟表的指针右转90°使用这9种作用，使得所有钟表都指向正上方(记为状态0)求使得总作用次数最少的策略SampleInputData3*3矩阵，元素为0，1，2或3，分别表示钟表指向上，右，下，左330222212钟表矩阵的有限性由于矩阵结构及其元素取值范围相当有限，故可能出现的钟表矩阵也是很有限的，即4^9=262144种由此有限性可以考虑搜索解法广度优先搜索从状态0开始搜索搜索过

2、程：标记可以通过一次作用达到此状态的所有状态为已搜索，然后搜索新标记的状态。搜索过程中保存使用的作用方式每个状态用一个32位整数的低18位表示,可将结果存在长度为262144的数组中广度优先搜索129155启发广度优先搜索的可行意味着作用次数的相当有限注意到作用的结果与作用的顺序无关，则显然每种作用最多只需使用3次于是，问题简化为求解同余方程组同余方程组把钟表和作用分别从1到9标号，则同余方程组可写为[C(i)+∑E(i,j)*M(j)]mod4=0(i=1..9)其中C(i),M(j),E(i,j)分别表示第i个钟表的初始状态，第j种作用的次数，第j种作用是否拨动

3、第i个钟表同余方程组写成矩阵的形式(C+EM)mod4=0(*)我们所求为M的最小非负解M0=Mmod4显然，当k足够大时，方程C+EM’=4*k的解也是(*)式的解，故M0=M’mod4同余方程组由于E是与输入无关的系数矩阵，所以我们可以事先求出其逆矩阵E，则M可以写成M=(E(4*k–C))mod4这样，我们只需用另一段程序求出E，问题就可以在O(1)的时空内解决。-1-100-1