2012感恩节最短源代码比赛solomon_007代码解析

lastwinner · 发表于 2012-12-4 13:35

solomon_007 发表于 2012-12-4 12:58
3，4，5 都只要保证3个，6，7就要求保证4个，8，9要保证5个。。。。

N格的情况需要保证这个N个当中每个格子都可以找到至少有一条M个格子相连的路径
N和M的关系为
M=trunc(N/2)+1

所以对于N=3个格子情况，实际上只需要保证每个格子都可以找到至少一条与2个格子就行了

solomon_007 · 发表于 2012-12-4 13:35

lastwinner 发表于 2012-12-4 13:31
这是我根据对称性推断出的，有效减少尝试次数，必能大大提高代码运行效率

原来要42秒，现在只要1秒啊

solomon_007 · 发表于 2012-12-4 13:38

lastwinner 发表于 2012-12-4 13:35
N格的情况需要保证这个N个当中每个格子都可以找到至少有一条M个格子相连的路径
N和M的关系为
M=trunc(N ...

对，你的描述更精确！

lastwinner · 发表于 2012-12-4 13:53

solomon_007 发表于 2012-12-4 13:33
我参赛的里面，那个游标条件是

a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+w+x+y=5

你这个思路还有可以改进的地方采用上述区域后，实际上如果我做这个题，我会在上述区域内考察如下情况：

5个方块横向连接在一起
4个方块横向连接在一起，1个方块在横向放置的这4个方块或上或下的不同位置放置
3个方块横向连接在一起，2个方块在横向放置的这3个方块或上或下的不同位置放置
至于2个方块和1个方块横向连接的就不用考虑了，因为通过上述三种情况得到的形状，经过旋转后就可得到，所以不必特殊考虑
旋转、镜像以上所得的形状，然后去重，即可得到所有系列的所有形状

这样处理后，你的代码框架可能会发生变化，但是效率还能更进一步提高。比如newkid在 http://www.itpub.net/forum.php?mod=viewthread&tid=1745501 提出的8个格子，你按你现在的思路去处理，估计还是会很耗费时间的

solomon_007 · 发表于 2012-12-4 14:06

lastwinner 发表于 2012-12-4 13:53
你这个思路还有可以改进的地方采用上述区域后，实际上如果我做这个题，我会在上述区域内考察如下情况：[/ ...

  with q as (select rownum-1 r from dual connect by level <3),
      p as (select a.r u,b.r v,c.r w,d.r x,e.r y from q a,q b,q c,q d,q e),
      t as (select a.u a,a.v b,a.w c,a.x d,a.y e,
                  b.u f,b.v g,b.w h,b.x i,b.y j,
                  c.u k,c.v l,c.w m,c.x n,c.y o,
                  d.u p,d.v q,d.w r,d.x s,d.y t,
                  e.u u,e.v v,e.w w,e.x x,e.y y
               from p a,p b,p c,p d,p e)
  select count(1)
from t
where a+b+c+d+e+f+g+h+i+k+l+m+p+q+u=5
   and a+b+c+d+e>0
   and a+f+k+p+u>0
   and v=0
   and r=0
   and n=0
   and j=0
   and w=0
   and s=0
   and o=0
   and x=0
   and t=0
   and y=0;
   and ( (a=1 and b=1 and c=1 and d=1 and e=1) --横着5个为1
      or (a=1 and b=1 and c=1 and d=1 and (f=1 or g=1 or h=1 or i=1) --横着4个为1
      or ( (k=1 and l=1 and m=1)
            or (f=1 and g=1 and h=1 ........--这样写有点多
            )
      )