Artifact 145a0b89a717cc17f81f3f80006e8c1bbe00a456:
0000: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0050: 0a 54 65 61 6d 3a 0a 20 20 44 61 72 6b 20 49 6e .Team:. Dark In
0060: 74 65 67 65 72 73 0a 0a 4d 65 6d 62 65 72 3a 0a tegers..Member:.
0070: 20 20 4b 61 7a 75 68 69 72 6f 20 49 6e 61 62 61 Kazuhiro Inaba
0080: 20 28 77 77 77 2e 6b 6d 6f 6e 6f 73 2e 6e 65 74 (www.kmonos.net
0090: 20 2f 20 6b 69 6b 69 40 6b 6d 6f 6e 6f 73 2e 6e / kiki@kmonos.n
00a0: 65 74 29 0a 0a 50 72 6f 67 72 61 6d 6d 69 6e 67 et)..Programming
00b0: 20 4c 61 6e 67 75 61 67 65 3a 0a 20 20 44 20 50 Language:. D P
00c0: 72 6f 67 72 61 6d 6d 69 6e 67 20 4c 61 6e 67 75 rogramming Langu
00d0: 61 67 65 20 28 64 6c 61 6e 67 2e 6f 72 67 29 0a age (dlang.org).
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0100: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0110: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0120: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0130: 0a 0a 54 68 72 65 65 20 74 79 70 65 73 20 6f 66 ..Three types of
0140: 20 73 6f 6c 76 65 72 73 20 61 72 65 20 63 6f 6d solvers are com
0150: 62 69 6e 65 64 2e 0a 0a 20 31 2e 20 53 6f 6c 76 bined... 1. Solv
0160: 65 72 20 22 46 6f 72 65 73 74 22 0a 20 20 20 20 er "Forest".
0170: 20 20 49 74 20 64 6f 65 73 20 62 72 65 61 64 74 It does breadt
0180: 68 20 66 69 72 73 74 20 73 65 61 72 63 68 20 65 h first search e
0190: 76 65 72 79 20 74 75 72 6e 20 66 6f 72 20 74 61 very turn for ta
01a0: 6b 69 6e 67 20 74 68 65 20 67 61 6d 65 27 73 20 king the game's
01b0: 64 79 6e 61 6d 69 73 6d 0a 20 20 20 20 20 20 69 dynamism. i
01c0: 6e 74 6f 20 61 63 63 6f 75 6e 74 2e 20 42 61 73 nto account. Bas
01d0: 69 63 61 6c 6c 79 20 69 74 20 74 72 69 65 73 20 ically it tries
01e0: 74 6f 20 72 75 73 68 20 74 6f 20 74 68 65 20 6e to rush to the n
01f0: 65 61 72 65 73 74 20 6c 61 6d 62 64 61 20 6f 72 earest lambda or
0200: 20 6f 70 65 6e 0a 20 20 20 20 20 20 6c 69 66 74 open. lift
0210: 2c 20 62 75 74 20 69 66 20 74 68 65 72 65 20 69 , but if there i
0220: 73 20 6e 6f 20 72 6f 75 74 65 20 66 6f 75 6e 64 s no route found
0230: 2c 20 69 74 20 74 72 69 65 73 20 6f 74 68 65 72 , it tries other
0240: 20 76 61 72 69 6f 75 73 20 6f 70 74 69 6f 6e 73 various options
0250: 2e 0a 20 20 20 20 20 20 50 75 73 68 69 6e 67 20 .. Pushing
0260: 72 6f 63 6b 73 2c 20 64 69 67 67 69 6e 67 20 65 rocks, digging e
0270: 61 72 74 68 20 61 72 6f 75 6e 64 20 72 6f 63 6b arth around rock
0280: 73 2c 20 77 61 69 74 20 61 20 77 68 69 6c 65 2e s, wait a while.
0290: 2e 2e 0a 20 20 20 20 20 20 49 74 20 69 73 20 73 ... It is s
02a0: 6c 6f 77 2c 20 62 75 74 20 72 65 6c 61 74 69 76 low, but relativ
02b0: 65 6c 79 20 6d 6f 72 65 20 63 6c 65 76 65 72 2e ely more clever.
02c0: 0a 0a 20 32 2e 20 53 6f 6c 76 65 72 20 22 57 69 .. 2. Solver "Wi
02d0: 6e 64 22 0a 20 20 20 20 20 20 49 74 20 64 6f 65 nd". It doe
02e0: 73 20 62 72 65 61 64 74 68 20 66 69 72 73 74 20 s breadth first
02f0: 73 65 61 72 63 68 20 61 6e 64 20 6d 65 6d 6f 72 search and memor
0300: 69 7a 65 20 74 68 65 20 63 6f 6d 70 75 74 65 64 ize the computed
0310: 20 70 61 74 68 2e 20 41 73 20 66 61 72 20 61 73 path. As far as
0320: 0a 20 20 20 20 20 20 70 6f 73 73 69 62 6c 65 2c . possible,
0330: 20 69 74 20 74 72 69 65 73 20 74 6f 20 66 6f 6c it tries to fol
0340: 6c 6f 77 20 74 68 65 20 70 72 65 63 6f 6d 70 75 low the precompu
0350: 74 65 64 20 72 6f 75 74 65 2e 20 49 66 20 73 6f ted route. If so
0360: 6d 65 20 6f 62 73 74 61 63 6c 65 20 69 73 0a 20 me obstacle is.
0370: 20 20 20 20 20 66 6f 75 6e 64 2c 20 69 74 20 72 found, it r
0380: 65 64 6f 65 73 20 74 68 65 20 42 46 53 2e 20 49 edoes the BFS. I
0390: 74 20 69 73 20 64 75 6d 62 20 62 75 74 20 66 61 t is dumb but fa
03a0: 73 74 2e 20 53 6f 20 69 74 20 69 73 20 75 73 65 st. So it is use
03b0: 64 20 66 6f 72 20 6c 61 72 67 65 0a 20 20 20 20 d for large.
03c0: 20 20 6d 61 70 73 2e 0a 0a 20 33 2e 20 53 6f 6c maps... 3. Sol
03d0: 76 65 72 20 22 46 69 72 65 22 0a 20 20 20 20 20 ver "Fire".
03e0: 20 49 74 20 69 73 20 61 20 6b 69 6e 64 20 6f 66 It is a kind of
03f0: 20 22 68 69 67 68 65 72 2d 6f 72 64 65 72 22 20 "higher-order"
0400: 73 6f 6c 76 65 72 2c 20 74 68 61 74 20 74 61 6b solver, that tak
0410: 65 73 20 61 6e 6f 74 68 65 72 20 73 6f 6c 76 65 es another solve
0420: 72 20 61 6e 64 0a 20 20 20 20 20 20 63 72 65 65 r and. cree
0430: 70 20 69 6e 74 6f 20 69 74 20 74 6f 20 6d 61 6b p into it to mak
0440: 65 20 69 74 20 6d 6f 72 65 20 63 61 72 65 66 75 e it more carefu
0450: 6c 2e 20 50 72 65 63 69 73 65 6c 79 20 73 70 65 l. Precisely spe
0460: 61 6b 69 6e 67 2c 20 74 68 69 73 20 68 69 67 68 aking, this high
0470: 65 72 0a 20 20 20 20 20 20 6f 72 64 65 72 20 73 er. order s
0480: 6f 6c 76 65 72 20 72 75 6e 73 20 74 68 65 20 73 olver runs the s
0490: 75 62 73 6f 6c 76 65 72 20 61 73 20 61 20 31 30 ubsolver as a 10
04a0: 2d 32 30 20 73 74 65 70 20 6c 6f 6f 6b 61 68 65 -20 step lookahe
04b0: 61 64 2e 20 57 68 69 6c 65 20 6e 6f 0a 20 20 20 ad. While no.
04c0: 20 20 20 70 72 6f 62 6c 65 6d 20 69 73 20 66 6f problem is fo
04d0: 75 6e 64 20 69 6e 20 74 68 65 20 6c 6f 6f 6b 61 und in the looka
04e0: 68 65 64 2c 20 69 74 20 62 65 68 61 76 65 73 20 hed, it behaves
04f0: 65 78 61 63 74 6c 79 20 61 73 20 73 61 6d 65 20 exactly as same
0500: 61 73 20 74 68 65 0a 20 20 20 20 20 20 73 75 62 as the. sub
0510: 20 73 6f 6c 76 65 72 2e 20 49 66 20 74 68 65 72 solver. If ther
0520: 65 20 77 61 73 20 61 20 70 72 6f 62 6c 65 6d 20 e was a problem
0530: 28 69 2e 65 2e 2c 20 73 75 62 73 6f 6c 76 65 72 (i.e., subsolver
0540: 20 64 65 61 64 20 6f 72 20 73 74 75 63 6b 29 2c dead or stuck),
0550: 0a 20 20 20 20 20 20 69 74 20 74 72 69 65 73 20 . it tries
0560: 61 6c 6c 20 74 68 65 20 70 6f 73 73 69 62 6c 65 all the possible
0570: 20 70 65 72 74 75 72 62 61 74 69 6f 6e 73 20 74 perturbations t
0580: 6f 20 74 68 65 20 6c 6f 6f 6b 61 68 65 61 64 20 o the lookahead
0590: 77 69 6e 64 6f 77 2c 20 61 6e 64 0a 20 20 20 20 window, and.
05a0: 20 20 72 65 2d 72 75 6e 73 20 73 75 62 73 6f 6c re-runs subsol
05b0: 76 65 72 73 20 6d 61 6e 79 20 74 69 6d 65 73 20 vers many times
05c0: 61 6e 64 20 63 68 6f 6f 73 65 73 20 74 68 65 20 and chooses the
05d0: 62 65 73 74 20 6f 6e 65 2e 0a 0a 46 69 72 65 3c best one...Fire<
05e0: 46 6f 72 65 73 74 3e 20 69 73 20 75 73 65 64 20 Forest> is used
05f0: 66 6f 72 20 57 2a 48 3c 3d 31 36 30 30 20 69 6e for W*H<=1600 in
0600: 73 74 61 6e 63 65 73 2e 20 46 69 72 65 3c 57 69 stances. Fire<Wi
0610: 6e 64 3e 20 69 73 20 75 73 65 64 20 66 6f 72 20 nd> is used for
0620: 61 6e 79 0a 69 6e 73 74 61 6e 63 65 73 2e 20 46 any.instances. F
0630: 6f 72 20 73 6d 61 6c 6c 65 72 20 6d 61 70 73 2c or smaller maps,
0640: 20 74 68 65 20 62 65 74 74 65 72 20 72 65 73 75 the better resu
0650: 6c 74 20 6f 66 20 74 68 65 20 74 77 6f 20 69 73 lt of the two is
0660: 20 75 73 65 64 20 61 73 20 74 68 65 0a 66 69 6e used as the.fin
0670: 61 6c 20 6f 75 74 70 75 74 2e 20 49 6e 20 61 64 al output. In ad
0680: 64 69 74 69 6f 6e 2c 20 61 6c 6c 20 74 68 65 73 dition, all thes
0690: 65 20 6f 75 74 70 75 74 73 20 61 72 65 20 67 75 e outputs are gu
06a0: 61 72 64 65 64 20 62 79 20 61 20 73 65 6e 74 69 arded by a senti
06b0: 6e 65 6c 0a 77 68 6f 20 61 62 6f 72 74 73 20 62 nel.who aborts b
06c0: 79 20 66 6f 72 63 65 20 74 68 65 20 6f 75 74 70 y force the outp
06d0: 75 74 20 73 65 71 75 65 6e 63 65 20 61 74 20 74 ut sequence at t
06e0: 68 65 20 62 65 73 74 20 73 63 6f 72 65 20 70 6f he best score po
06f0: 73 69 74 69 6f 6e 20 28 73 6f 0a 74 68 61 74 20 sition (so.that
0700: 6c 65 66 74 2d 6f 76 65 72 20 72 75 6e 20 64 6f left-over run do
0710: 65 73 20 6e 6f 74 20 6d 61 6b 65 20 74 68 65 20 es not make the
0720: 73 63 6f 72 65 20 77 6f 72 73 65 29 2e 0a 0a 0a score worse)....
0730: 0a 46 6f 72 20 74 68 65 20 61 64 64 65 64 20 66 .For the added f
0740: 65 61 74 75 72 65 73 2c 20 6e 6f 74 20 71 75 69 eatures, not qui
0750: 74 65 20 6d 75 63 68 20 65 66 66 6f 72 74 20 69 te much effort i
0760: 73 20 70 61 69 64 2e 20 53 6f 20 69 66 20 74 68 s paid. So if th
0770: 65 72 65 20 63 61 6d 65 20 61 0a 6d 61 70 20 74 ere came a.map t
0780: 68 61 74 20 66 75 6c 6c 79 20 65 78 70 6c 6f 69 hat fully exploi
0790: 74 73 20 74 68 65 20 63 68 61 72 61 63 74 65 72 ts the character
07a0: 69 73 74 69 63 73 20 6f 66 20 74 68 65 20 67 61 istics of the ga
07b0: 64 67 65 74 73 2c 20 49 27 6c 6c 20 6c 6f 73 65 dgets, I'll lose
07c0: 20 3a 28 2e 0a 0a 20 20 46 6c 6f 6f 64 3a 0a 20 :(... Flood:.
07d0: 20 20 20 20 41 6c 6d 6f 73 74 20 6e 6f 74 68 69 Almost nothi
07e0: 6e 67 20 69 73 20 64 6f 6e 65 20 66 6f 72 20 69 ng is done for i
07f0: 74 2e 20 54 68 65 20 22 66 69 72 65 22 20 73 6f t. The "fire" so
0800: 6c 76 65 72 20 6c 6f 63 61 6c 6c 79 20 74 61 6b lver locally tak
0810: 65 73 20 63 61 72 65 0a 20 20 20 20 20 6f 66 20 es care. of
0820: 69 74 2c 20 61 6e 64 20 69 74 20 69 73 20 69 6e it, and it is in
0830: 63 6c 69 64 65 64 20 74 6f 20 75 73 65 20 22 55 clided to use "U
0840: 22 20 64 75 72 69 6e 67 20 70 65 72 74 75 72 62 " during perturb
0850: 61 74 69 6f 6e 2e 20 41 6c 73 6f 2c 20 22 77 69 ation. Also, "wi
0860: 6e 64 22 0a 20 20 20 20 20 73 6f 6c 76 65 72 27 nd". solver'
0870: 73 20 42 46 53 20 69 73 20 6d 61 64 65 20 74 6f s BFS is made to
0880: 20 6c 69 6b 65 20 22 55 22 20 64 69 72 65 63 74 like "U" direct
0890: 69 6f 6e 20 69 6e 20 6c 61 72 67 65 72 20 6d 61 ion in larger ma
08a0: 70 73 2e 0a 20 20 54 72 61 6d 70 6f 6c 69 6e 65 ps.. Trampoline
08b0: 3a 0a 20 20 20 20 20 4a 75 73 74 20 74 72 65 61 :. Just trea
08c0: 74 65 64 20 61 73 20 6f 6e 65 20 42 46 53 20 65 ted as one BFS e
08d0: 64 67 65 2e 0a 20 20 42 65 61 72 64 3a 0a 20 20 dge.. Beard:.
08e0: 20 20 20 4e 6f 20 63 6c 75 65 2e 20 49 66 20 74 No clue. If t
08f0: 68 65 72 65 20 69 73 20 6e 6f 74 68 69 6e 67 20 here is nothing
0900: 65 6c 73 65 20 74 6f 20 64 6f 2c 20 67 6f 65 73 else to do, goes
0910: 20 74 6f 20 74 68 65 20 70 6c 61 63 65 20 77 68 to the place wh
0920: 65 72 65 20 6d 61 6e 79 0a 20 20 20 20 20 57 61 ere many. Wa
0930: 64 6c 65 72 27 73 20 61 72 65 20 61 72 6f 75 6e dler's are aroun
0940: 64 2c 20 61 6e 64 20 75 73 65 73 20 74 68 65 20 d, and uses the
0950: 73 68 61 76 65 72 2e 0a 20 20 48 69 67 68 65 72 shaver.. Higher
0960: 2d 6f 72 64 65 72 20 52 6f 63 6b 73 3a 0a 20 20 -order Rocks:.
0970: 20 20 20 54 72 69 65 73 20 74 6f 20 70 75 73 68 Tries to push
0980: 20 74 68 65 6d 20 73 6f 6d 65 68 6f 77 20 72 61 them somehow ra
0990: 6e 64 6f 6d 6c 79 2e 0a 0a 0a 0a 54 68 61 6e 6b ndomly.....Thank
09a0: 73 20 66 6f 72 20 6f 72 67 61 6e 69 7a 69 6e 67 s for organizing
09b0: 20 74 68 65 20 63 6f 6e 74 65 73 74 21 20 49 27 the contest! I'
09c0: 76 65 20 65 6e 6a 6f 79 65 64 21 0a ve enjoyed!.