请用pl/sql解欧拉计划594题:菱形划分法

newkid · 发表于 2017-4-11 22:56

〇〇发表于 2017-4-11 06:34
回溯法怎么个思路？

回溯法就是教科书里说的那样，还有什么好说的？
搞一个数组做堆栈，把图形一个接一个往里放。拼的时候让它们互相衔接，就是加入一个之后查找它的空闲边再接上另一个。每条边度数为2则已满，为1则空闲。一开始只有边框是空闲的。从一条边接上另一个图形通常有三种选择，回溯的时候就是尝试其它不同选择。填满或者碰到死角就回溯。
这个数组最多也就几百字节，内存是很省的。

大图分解成小一号图的思路现在看不到可行性。

〇〇 · 发表于 2017-4-12 02:53

那人算到On,2超过几百亿一定不是逐个加的

newkid · 发表于 2017-4-12 04:53

那就是存在着把大图分解成小图的方法，只是我们看不出来。

〇〇 · 发表于 2017-4-12 07:49

newkid 发表于 2017-4-12 04:53
那就是存在着把大图分解成小图的方法，只是我们看不出来。

只能希望我的穷举程序在合理时间内算对，到pe论坛去看别人思路了

〇〇 · 发表于 2017-4-12 10:47

newkid 发表于 2017-4-11 22:56
回溯法就是教科书里说的那样，还有什么好说的？
搞一个数组做堆栈，把图形一个接一个往里放。拼的时候让 ...

那我还得把共享某个边的图形都列出来，才能进行选择

〇〇 · 发表于 2017-4-12 20:15

newkid 发表于 2017-4-10 21:57
应该是五个吧。但是这个问题有什么意义？按我的设想，这就是一个占用标记而已，决定了一个图能不能往上放 ...

怎么才能不重不漏?现在我是利用形状编号大小排序,如果找邻居,就不是这个顺序了.请给个伪代码吧,

newkid · 发表于 2017-4-12 22:14

〇〇发表于 2017-4-12 10:47
那我还得把共享某个边的图形都列出来，才能进行选择

这有什么难的？一个小小SQL就轻松搞定，这些都是回溯开始之前的准备工作。
你把算法想清楚之后，就要设计一系列数据结构来支持它，所有能够事先计算的就要先算好备用。
伪代码写起来工作量和真代码差不多，我只能像前面那样用语言描述。
不重：找邻居的时候只需从一条边出发。其它的边最终会被拼回来。
不漏：最多可能有三种邻居，回溯的时候每种都不放过。
你可以用任何手段，任何对象都可以编号，这就是算法开始之前的准备工作。

〇〇 · 发表于 2017-4-13 21:39

上网看了回溯法，似乎我的递归也算回溯，要改成迭代挺麻烦的

newkid · 发表于 2017-4-14 05:16

奇怪，我代码贴不出来。不知道抽什么风。

newkid · 发表于 2017-4-14 05:21

再试试：

drop type tbl_edge;

create or replace  type t_edge is object (
   eid  integer
   ,x1 integer
   ,y1 integer
   ,x2 integer
   ,y2 integer
   ,direction integer
   ,cell integer
   ,degree integer
   )
/

create type tbl_edge is table of t_edge
/

drop type tbl_g;

create or replace type t_g is object (
   gid integer
   ,eid1  integer
   ,eid2  integer
   ,eid3  integer
   ,eid4  integer
   ,c1  integer
   ,c2  integer
   ,c3  integer
   ,c4  integer
   ,area  integer
)
/

create type tbl_g is table of t_g
/

CREATE OR REPLACE PROCEDURE p594 (p_m in number,p_n in number)
as

type t_n1 is table of number index by pls_integer;
type t_n2 is table of t_n1 index by pls_integer;
type t_n3 is table of t_n2 index by pls_integer;

v_neighbour t_n3;

v_e tbl_edge;
v_g tbl_g;

v_b1 number :=0;
v_b2 number :=0;
v_b3 number :=0;
v_b4 number :=0;

v_area number :=0;
v_total number := (p_m+2*p_n)*(p_m+2*p_n) - p_n*p_n*2;  ---- 铺满的总面积

type t_stack is record (
      eid  number
   ,g t_n1
   ,g_cnt number
   ,current_g number
   ,gid  number
   );

type ta_stack is table of t_stack index by pls_integer;

v_stack ta_stack;
v_top number;
v_gid number;
v_found number :=0;

v_str varchar2(500);

procedure find_edge
is
   v_ptr number := v_top;
   v_gid number;
   v_ret number;
begin
   while v_ptr>1 loop
         v_gid := v_stack(v_ptr).gid;
         v_ret := case when v_e(v_g(v_gid).eid1).degree=1 then v_g(v_gid).eid1
                        when v_e(v_g(v_gid).eid2).degree=1 then v_g(v_gid).eid2
                        when v_e(v_g(v_gid).eid3).degree=1 then v_g(v_gid).eid3
                        when v_e(v_g(v_gid).eid4).degree=1 then v_g(v_gid).eid4
                        ---- else: 闭合区域
                  end;

         if v_ret is not null then

            begin
                     v_stack(v_top).g := v_neighbour(v_gid)(v_ret);
                     v_stack(v_top).g_cnt := v_stack(v_top).g.count;
                     v_stack(v_top).eid := v_ret;
            exception
               when no_data_found then
                     v_stack(v_top).g_cnt :=-1;
            end;

            return;
         end if;
         v_ptr := v_ptr-1;
   end loop;

   v_stack(v_top).g_cnt :=-1;
   return;

end find_edge;

begin

   WITH v AS ( ---- 所有点坐标：X=[0,M+2N] , Y=[0,M+2N]
   SELECT X,Y,ROW_NUMBER() OVER(ORDER BY X,Y) VID
   FROM (SELECT LEVEL-1 X FROM DUAL CONNECT BY LEVEL<=P_M+2*P_N+1)
         ,(SELECT LEVEL-1 Y FROM DUAL CONNECT BY LEVEL<=P_M+2*P_N+1)
   WHERE NOT (Y<-X+P_N             --- 排除点：左下角
            OR Y>X+P_M+P_N       --- 左上角
            OR Y>-X+2*P_M+3*P_N --- 右上角
            OR Y<X-P_M-P_N       --- 右下角
            )
   )
   ---所有边
   SELECT t_edge(eid  --integer
               ,x1 --integer
               ,y1 --integer
               ,x2 --integer
               ,y2 --integer
               ,direction
         --------一共(M+2N)^2个格子CELL，编号方法：从下至上，从左至右，从0到(M+2N)^2-1:
         ----------每个斜线求出位于哪个格子，每个垂直线求出右侧的格子编号。这是为了构造每个小图所覆盖的格子
         ----------每个cell分四个区：
         -----    ____
         -----    |\1 /|
         -----    | \/ |
         -----    |4/\2|
         -----    |/3_\|
         ,CASE WHEN direction IN (1,3) AND x1<P_M+2*P_N THEN
                  y1*(P_M+2*P_N)+x1
               WHEN direction =4 AND x1<P_M+2*P_N THEN
                  (y1-1)*(P_M+2*P_N)+x1
         END --AS cell
            ,CASE WHEN Y IN (-X+P_N  --- 左下角
                              ,X+P_M+P_N       --- 左上角
                              ,-X+2*P_M+3*P_N --- 右上角
                              ,X-P_M-P_N       --- 右下角
                              ,0                --- 下横边
,P_M+2*P_N       --- 上横边
                              )
                        or X IN (0,P_M+2*P_N) --- 左右纵向边框
                  THEN 1
                  ELSE 0
               END
               )
   BULK COLLECT INTO v_e
   FROM (
         SELECT ROW_NUMBER() OVER(ORDER BY v1.vid,v2.vid) eid
               ,v1.x x1,v1.y y1
               ,v2.x x2,v2.y y2
               ,CASE WHEN v1.x=v2.x THEN 1  --- 垂直
                     WHEN v1.y=v2.y THEN 2  --- 水平
                     WHEN v1.y<v2.y THEN 3  --- 左下至右上
                     ELSE 4 --左上至右下
                  END as direction
               ,(v1.x+v2.x)/2 as x  --- 线段中点坐标，用于判断是否在边框上
               ,(v1.y+v2.y)/2 as y
            FROM v v1,v v2
            WHERE v1.vid<v2.vid ---- 方向：由下至上，由左至右，左下至右上，左上至右下
                  AND ABS(v1.x-v2.x) IN (0,1)
                  AND ABS(v1.y-v2.y) IN (0,1)
         ) ee
   ORDER BY eid
   ;

WITH g as ( ---- 小图, 求出它们的边以及占用格子区域的二进制掩码
SELECT ROW_NUMBER() OVER(ORDER BY e1.eid,e2.eid,e3.eid,e4.eid) as gid
      ,e1.eid eid1
      ,e2.eid eid2
      ,e3.eid eid3
      ,e4.eid eid4
      ,POWER(2,CASE WHEN e1.direction =1 AND e2.direction =2 THEN e1.cell
                     WHEN e1.direction =1 AND e2.direction =3 THEN e4.cell
                     WHEN e1.direction =1 AND e2.direction =4 THEN e4.cell
                     WHEN e1.direction =3 AND e2.direction =4 THEN e3.cell
                     WHEN e1.direction =3 AND e2.direction =2 THEN e3.cell
                     WHEN e1.direction =4 AND e2.direction =2 THEN e1.cell
               END)
         +CASE WHEN e1.direction =3 AND e2.direction =4 THEN POWER(2,e4.cell) ELSE 0 END as c1 ---占了哪个cell的第一区。如果大方块有两个CELL
      ,POWER(2,CASE WHEN e1.direction =1 AND e2.direction =2 THEN e1.cell
                     WHEN e1.direction =1 AND e2.direction =3 THEN e2.cell
                     WHEN e1.direction =1 AND e2.direction =4 THEN e4.cell
                     WHEN e1.direction =3 AND e2.direction =4 THEN e1.cell
                     WHEN e1.direction =3 AND e2.direction =2 THEN e1.cell
                     WHEN e1.direction =4 AND e2.direction =2 THEN e1.cell
               END)
         +CASE WHEN e1.direction =3 AND e2.direction =4 THEN POWER(2,e4.cell) ELSE 0 END as c2
      ,POWER(2,CASE WHEN e1.direction =1 AND e2.direction =2 THEN e1.cell
                     WHEN e1.direction =1 AND e2.direction =3 THEN e2.cell
                     WHEN e1.direction =1 AND e2.direction =4 THEN e2.cell
                     WHEN e1.direction =3 AND e2.direction =4 THEN e1.cell
                     WHEN e1.direction =3 AND e2.direction =2 THEN e1.cell
                     WHEN e1.direction =4 AND e2.direction =2 THEN e3.cell
               END)
         +CASE WHEN e1.direction =3 AND e2.direction =4 THEN POWER(2,e2.cell) ELSE 0 END as c3
      ,POWER(2,CASE WHEN e1.direction =1 AND e2.direction =2 THEN e1.cell
                     WHEN e1.direction =1 AND e2.direction =3 THEN e4.cell
                     WHEN e1.direction =1 AND e2.direction =4 THEN e2.cell
                     WHEN e1.direction =3 AND e2.direction =4 THEN e2.cell
                     WHEN e1.direction =3 AND e2.direction =2 THEN e3.cell
                     WHEN e1.direction =4 AND e2.direction =2 THEN e3.cell
               END)
         +CASE WHEN e1.direction =3 AND e2.direction =4 THEN POWER(2,e3.cell) ELSE 0 END as c4
      , CASE WHEN e1.direction =3 AND e2.direction =4 THEN 2 ELSE 1 END as area ---面积
   FROM TABLE(v_e) e1,TABLE(v_e) e2,TABLE(v_e) e3, TABLE(v_e) e4
   WHERE (e1.direction =1 AND e2.direction IN (2,3,4)  ---- 小正方型及纵向直边菱形
         OR e1.direction =3 AND e2.direction =4  ---- 大正方型
         OR e1.direction IN (3,4) AND e2.direction =2  ---- 纵向斜边菱形
         )
         AND e3.direction=e1.direction
         AND e4.direction=e2.direction
         AND e1.x2=e2.x1 AND e1.y2=e2.y1
         AND e2.x2=e3.x2 AND e2.y2=e3.y2
         AND e3.x1=e4.x2 AND e3.y1=e4.y2
)
SELECT t_g(
   gid  --  integer
   ,eid1 --  integer
   ,eid2 --  integer
   ,eid3 --  integer
   ,eid4 -- integer
   ,c1 -- integer
   ,c2 -- integer
   ,c3 -- integer
   ,c4 -- integer
   ,area
   )
   BULK COLLECT INTO v_g
   FROM g
   ORDER BY gid;

for lv_rec in (
      WITH ge as (
         SELECT gid,decode(n,1,eid1,2,eid2,3,eid3,4,eid4) eid,c1,c2,c3,c4 FROM TABLE(v_g) g,(SELECT LEVEL n from dual connect by level<=4)
      )
      select g1.gid,g1.eid,g2.gid gid2,ROW_NUMBER() OVER(PARTITION BY g1.gid,g1.eid ORDER BY g2.gid) rn
         from ge g1,ge g2
      where g1.gid<>g2.gid and g1.eid=g2.eid
            and bitand(g1.c1,g2.c1)=0 and bitand(g1.c2,g2.c2)=0 and bitand(g1.c3,g2.c3)=0 and bitand(g1.c4,g2.c4)=0
) loop
   v_neighbour(lv_rec.gid)(lv_rec.eid)(lv_rec.rn) :=lv_rec.gid2;
end loop;

v_top :=1;
v_stack(v_top).eid :=1;

for lv_rec in (
      WITH ge as (
         SELECT gid,decode(n,1,eid1,2,eid2,3,eid3,4,eid4) eid,c1,c2,c3,c4 FROM TABLE(v_g) g,(SELECT LEVEL n from dual connect by level<=4)
      )
      select ge.gid,rownum rn
         from ge
      where ge.eid=1
) loop
   v_stack(v_top).g(lv_rec.rn) := lv_rec.gid;
end loop;
v_stack(v_top).g_cnt := v_stack(v_top).g.count;
v_stack(v_top).current_g :=0;

while v_top>0 loop

      v_stack(v_top).current_g := v_stack(v_top).current_g +1;

      if v_stack(v_top).current_g <= v_stack(v_top).g_cnt then

            v_gid :=v_stack(v_top).g(v_stack(v_top).current_g);

            if bitand(v_b1,v_g(v_gid).c1)=0 and bitand(v_b2,v_g(v_gid).c2)=0 and bitand(v_b3,v_g(v_gid).c3)=0 and bitand(v_b4,v_g(v_gid).c4)=0 then
               if v_area + v_g(v_gid).area = v_total then
                  v_found := v_found+1;
                  -- v_str := '';
                  -- for i in 2..v_top loop
                  --    v_str := v_str||v_stack(i).gid||',';
                  -- end loop;
                  continue;
               end if;

               v_top := v_top+1;

               v_stack(v_top).gid := v_gid;
               v_area := v_area + v_g(v_gid).area;
               v_b1 := v_b1 + v_g(v_gid).c1;
               v_b2 := v_b2 + v_g(v_gid).c2;
               v_b3 := v_b3 + v_g(v_gid).c3;
               v_b4 := v_b4 + v_g(v_gid).c4;

               v_e(v_g(v_gid).eid1).degree := v_e(v_g(v_gid).eid1).degree+1;
               v_e(v_g(v_gid).eid2).degree := v_e(v_g(v_gid).eid2).degree+1;
               v_e(v_g(v_gid).eid3).degree := v_e(v_g(v_gid).eid3).degree+1;
               v_e(v_g(v_gid).eid4).degree := v_e(v_g(v_gid).eid4).degree+1;


               find_edge;

               if v_stack(v_top).eid is null then
                  for i in 1..v_top loop
                     dbms_output.put_line(i||'='||v_stack(i).gid);
                  end loop;
                  v_stack(v_top).current_g :=0;
               else

                  v_stack(v_top).current_g :=0;

               end if;
            end if;
      end if;

      if v_stack(v_top).current_g > v_stack(v_top).g_cnt then
         if v_top=1 then
            exit;
         end if;

         v_gid := v_stack(v_top).gid;

         v_area := v_area - v_g(v_gid).area;
         v_b1 := v_b1 - v_g(v_gid).c1;
         v_b2 := v_b2 - v_g(v_gid).c2;
         v_b3 := v_b3 - v_g(v_gid).c3;
         v_b4 := v_b4 - v_g(v_gid).c4;

         v_e(v_g(v_gid).eid1).degree := v_e(v_g(v_gid).eid1).degree-1;
         v_e(v_g(v_gid).eid2).degree := v_e(v_g(v_gid).eid2).degree-1;
         v_e(v_g(v_gid).eid3).degree := v_e(v_g(v_gid).eid3).degree-1;
         v_e(v_g(v_gid).eid4).degree := v_e(v_g(v_gid).eid4).degree-1;

         v_top := v_top-1;  -- 回溯

      end if;
end loop;

dbms_output.put_line('total found:'||v_found);

end;
/

exec p594(2,1);
total found:76

exec p594(3,2);
total found:456572

PL/SQL procedure successfully completed.

Elapsed: 00:01:42.89