ACM题(#2634 Collecting Stones)

〇〇

SQL> exec :m:=2080

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.01
SQL> /
^[^[^[^[


WITH d AS (
*
ERROR at line 1:
ORA-01013: user requested cancel of current operation


Elapsed: 16:21:49.35

〇〇

SQL> exec :m:=1074

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\26345

T.PATH||'*'||T2.PATH
-----------------------------------------------------------------------------------------------------------
,01,09,18,27,36*45,37,29,21,13,05,06,14,22,30,38,46,54,62,63,55,47,39,31,23,15,08,16,24,32,40,48,56,64,

已用时间:  00: 10: 50.78
SQL> exec :m:=1100

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\26345

T.PATH||'*'||T2.PATH
----------------------------------------------------------------------------------------------------------
,01,09,17,26,27,36*45,37,29,21,13,05,14,22,30,38,46,54,62,63,55,47,39,31,23,15,07,08,16,24,32,40,48,56,64,

已用时间:  00: 46: 48.92

〇〇

SQL> exec :m:=1374

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\26345

T.PATH||'*'||T2.PATH
---------------------------------------------------------------------------------------------------------------------
,01,09,17,25,33,41,50,59,60*61,53,45,37,29,21,13,22,30,38,46,54,62,63,55,47,39,31,23,15,07,08,16,24,32,40,48,56,64,

已用时间:  13: 51: 04.32

rollingpig

原题中任意一个grid的stone数不明啊

On each grid, there are less than 2000001 stones

〇〇

原帖由 rollingpig 于 2011-4-11 09:53 发表
原题中任意一个grid的stone数不明啊

On each grid, there are less than 2000001 stones

他那个自由度太大，我觉得1-100随机排列就可以，m在
sum(all)和sum(least 8)之间。。

rollingpig

这时候再使用probe level=4 再加上通过translate避免交叉，岂不是和我的做法更类似？

原帖由 〇〇 于 2011-4-9 17:05 发表
把grid看作城市，stone看作里程，这道题就和第3题很像，不过变成给了固定的车费，怎么从起点到终点刚好花完

〇〇

随机数
WITH d AS (
select 01 id,1 r,1 c,87 val from dual union
select 02,1,2,11 from dual union
select 03,1,3,26 from dual union
select 04,1,4,35 from dual union
select 05,1,5,89 from dual union
select 06,1,6, 1 from dual union
select 07,1,7,32 from dual union
select 08,1,8,37 from dual union
select 09,2,1,33 from dual union
select 10,2,2,22 from dual union
select 11,2,3,57 from dual union
select 12,2,4,52 from dual union
select 13,2,5,17 from dual union
select 14,2,6, 5 from dual union
select 15,2,7,39 from dual union
select 16,2,8,93 from dual union
select 17,3,1,64 from dual union
select 18,3,2,98 from dual union
select 19,3,3,63 from dual union
select 20,3,4,11 from dual union
select 21,3,5, 3 from dual union
select 22,3,6,25 from dual union
select 23,3,7,93 from dual union
select 24,3,8,86 from dual union
select 25,4,1, 2 from dual union
select 26,4,2,72 from dual union
select 27,4,3,17 from dual union
select 28,4,4,87 from dual union
select 29,4,5,38 from dual union
select 30,4,6,77 from dual union
select 31,4,7,51 from dual union
select 32,4,8,19 from dual union
select 33,5,1,48 from dual union
select 34,5,2,15 from dual union
select 35,5,3,52 from dual union
select 36,5,4,85 from dual union
select 37,5,5,68 from dual union
select 38,5,6,81 from dual union
select 39,5,7,96 from dual union
select 40,5,8,90 from dual union
select 41,6,1,99 from dual union
select 42,6,2,20 from dual union
select 43,6,3,83 from dual union
select 44,6,4,91 from dual union
select 45,6,5,26 from dual union
select 46,6,6,40 from dual union
select 47,6,7, 9 from dual union
select 48,6,8,88 from dual union
select 49,7,1,24 from dual union
select 50,7,2,50 from dual union
select 51,7,3,32 from dual union
select 52,7,4,74 from dual union
select 53,7,5,93 from dual union
select 54,7,6,52 from dual union
select 55,7,7,56 from dual union
select 56,7,8,89 from dual union
select 57,8,1,82 from dual union
select 58,8,2,42 from dual union
select 59,8,3,22 from dual union
select 60,8,4,28 from dual union
select 61,8,5,77 from dual union
select 62,8,6,83 from dual union
select 63,8,7,56 from dual union
select 64,8,8,80 from dual)

〇〇

怪事，stone有序总是后面的路线长，随机以后，前面长了
SQL> exec :m:=500

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> @c:\downloads\263457

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,1,2,11,20*13,22,31,39,47,55,64,

已用时间:  00: 00: 00.32
SQL> exec :m:=900

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> @c:\downloads\263457

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,1,9,17,25,18,26,34,42,50,59,60,52,44*37,46,55,64,

已用时间:  00: 00: 03.47
SQL> exec :m:=1100

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\263457

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,1,9,17,25,34,42,50,58,59,51,43,35,27,19,20,28,36,44*37,46,55,64,

已用时间:  00: 00: 05.08
SQL> exec :m:=1600

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\263457

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,1,9,17,25,33,41,49,57,58,50,42,34,26,18,10,2,11,19,27,35,43,36,44,52,60*53,54,63,64,

已用时间:  00: 00: 05.63
SQL> exec :m:=1800

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\263457

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,1,9,17,25,33,41,49,58,50,42,34,26,18,10,11,19,27,35,43,51,59,60,52,44,36,28*21,30,39,48,56,64,

已用时间:  00: 00: 05.83
SQL> exec :m:=2000

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.02
SQL> @c:\downloads\263457

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,1,9,17,25,33,41,49,57,58,50,42,34,26,18,10,2,3,11,19,27,35,43,51,59,60,52,44,36,28*21,30,38,39,48,56,64,

已用时间:  00: 00: 06.71
SQL> exec :m:=2800

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> @c:\downloads\263457

T.PATH||'*'||T2.PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
,1,9,17,25,33,41,49,57,58,50,42,34,26,18,10,2,3,11,19,27,35,43,51,59,60,52,44,36,28,20,12*5,13,22,30,38,46,54,47,39,31,23,15,8,16,24,32,40,48,56,64,

已用时间:  00: 02: 47.84
SQL>

lugionline

别幼稚了，这个题目能用构造路径算出来？

你把M设置成最大值或者设置成不可能的值看看（比方去掉10这个数字），会有多少路径？

人家只要你回答是或者否，并没有让你找出所有路径，这是有原因的

rollingpig

拿我的第三题答案修改了一下，没有特小心的看过。
:LL控制level, 可以上下改改试试。

1. 
   
2. var m number
   
3. var ll number
   
4. exec :m:=374 ;:LL:=4
   
5. 
   
6. WITH
   
7. routes2way(srcblock,destblock,stones) AS( -- 把grid里的blocknumber改为相应的blockud,同时，构造双向通道表。
   
8. select chr(BLOCKNUMBER-8),chr(BLOCKNUMBER),stones from grid where BLOCKNUMBER>8 -- Move down
   
9. union all
   
10. select chr(BLOCKNUMBER+8),chr(BLOCKNUMBER),stones from grid where BLOCKNUMBER<57 --Move up
    
11. union all
    
12. select chr(BLOCKNUMBER-1),chr(BLOCKNUMBER),stones from grid where mod(blocknumber,8)!=1 --Move right
    
13. union all
    
14. select chr(BLOCKNUMBER-9),chr(BLOCKNUMBER),stones from grid where mod(blocknumber,8)!=1 and BLOCKNUMBER>8  --Move down right
    
15. union all
    
16. select chr(BLOCKNUMBER+7),chr(BLOCKNUMBER),stones from grid where mod(blocknumber,8)!=1 and BLOCKNUMBER<57  --Move up right
    
17. ) ,
    
18. pathprobe (levelN,srcblock,destblock,totalstones,pathstr,pathstr2) AS ( --先探测3级内的路径
    
19.   SELECT 1, srcblock,destblock,routes2way.stones,cast(srcblock||destblock as varchar2(4000)),cast(ascii(srcblock)||'+'||ascii(destblock) as varchar2(4000))
    
20.    FROM routes2way
    
21.   UNION ALL
    
22.   SELECT        levelN+1,--限制递归层数
    
23.   a.srcblock,b.destblock,--出发、到达block
    
24.   a.totalstones + b.stones,--stones
    
25.         pathstr||b.destblock, --keep path
    
26.         pathstr2||'+'||ascii(b.destblock) --keep path
    
27.   FROM  pathprobe a , routes2way b
    
28.   WHERE        a.destblock = b.srcblock --join
    
29.   AND        instr(pathstr,b.destblock)=0 --no duplicated
    
30.   AND        levelN<:LL-1 --control level
    
31.   AND a.totalstones + b.stones <=:M
    
32. ),
    
33. pathprobe2 as(
    
34. select * from  pathprobe
    
35. where (leveln=:ll-1 or destblock = chr(64)) --除了尾吧，其他的都是整段的
    
36. and instr(pathstr,chr(1))<2
    
37. and (instr(pathstr,chr(64))>length(pathstr)-1 or instr(pathstr,chr(64))=0)
    
38. ),
    
39. fullpath (levelM,srcblock,destblock,totalstones,totalstones2,pathstr,pathstr2) AS ( --full path
    
40.   SELECT        1 ,srcblock,destblock,totalstones+stones,0,pathstr,pathstr2
    
41.   FROM
    
42.   pathprobe2 , grid
    
43.    where srcblock =  chr(1)  and grid.blocknumber=1    -- Start with first block
    
44.   UNION ALL
    
45.   SELECT        levelM+1,a.srcblock,b.destblock,a.totalstones + b.totalstones,b.totalstones,
    
46.     a.pathstr||substr(b.pathstr,2), --继续拼path,其中a.pathstr最后一位=b.pathstr的第一位
    
47.     substr(a.pathstr2,1,instr(a.pathstr2,'+',-1))||b.pathstr2 --继续拼path,其中a.pathstr最后一位=b.pathstr的第一位
    
48.   FROM
    
49.   fullpath a , pathprobe2 b
    
50.   WHERE        a.destblock = b.srcblock
    
51.   AND        translate(a.pathstr,chr(254)||substr(b.pathstr,2),chr(254)) = a.pathstr
    
52.   --第二个path的字母第一位和之前path最后一位重复，其他没有重复，不往回头路,只有使用单字符才能利用translate来判断。
    
53.   and  a.totalstones + b.totalstones <=:M     -- Control number
    
54. )
    
55. select  * from  fullpath
    
56.   where     destblock = chr(64)  --End with lastblock
    
57.    and  totalstones=:m
    
58. 
    

复制代码