Posted on 2009-03-08 11:35
杜仲当归 阅读(353)
评论(0) 编辑 收藏 引用
一道相当BT的搜索题，写了300+行数。更BT的是前前后后写了五六遍，几种搜索策略都离通过最后两个点差之毫厘，最终还是加了剪枝才过的。一道题写了1K行以上的代码量，也算是罕古未见了!
此题首先要明确搜索顺序。限制条件最多的是第五行和第五列，然后对角线也可以控制较多行列，之后是第一行和第一列，最后减法得到剩下四个数，判断即可。
但是这样仍然过不了23 7这样的数据。于是加入剪枝：在搜索完第五行第五列的同时，发现有四行已经填上了三个数，且都是X3X77这样的排列。因此可以预先建立表，判断出第2，4，5位已知的数是否可能为质数，不满足者剪枝。
在搜索每一行列的时候注意已填入的信息，为此要建立已知第1位，第3位，第5位的质数表。