Discussion @ 1589. Sokoban @ Timus Online Judge

Oracle[Lviv NU] TLE #62 [4] // Problem 1589. Sokoban 3 Nov 2009 20:40

Can somebody give me some hard test - my program works fine on all tests, which I can think out. BTW, here is some of them:

########
#.OOOOO#
#$O$O$O#
#OO$O$O#
#@O$O$O#
###***O#
#......#
########

########
#.O$OO.#
#O$..$O#
#$$..$O#
#O$..$$#
#@$O.$O#
#..$OO.#
########

########
#.O$OO.#
#O$..$O#
#$$..$O#
#O$..$$#
#@$..$O#
#.O$OO.#
########

########
#......#
###***O#
#@O$O$O#
#OO$O$O#
#$O$O$O#
#.OOOOO#
########

########
#.....O#
#$$$$$O#
#OO...O#
#$$$$$O#
#O.OO$.#
#.O$.$+#
########

########
#......#
###***O#
#@O$O$O#
#OO$O$O#
#OO$O$O#
#OOOOOO#
########

########
#.$.$OO#
#@OOOOO#
#O$$$$$#
#O.....#
#$$$$$$#
#......#
########

########
#.OOO.O#
#@$O##O#
#OOO*OO#
#.$O$O$#
#$$$$..#
#...OOO#
########

########
#OOOO.O#
#@OO##O#
#OOO*OO#
#.$O$OO#
#$$$$.O#
#...OOO#
########

#######
#@$OO.#
#$O$OO#
#.O.OO#
#######

P.S. space I've changed to O.

Edited by author 03.11.2009 20:42

Oracle[Lviv NU] Re: TLE #62 [3] // Problem 1589. Sokoban 7 Nov 2009 03:54

AC finally.

Vitalii Arbuzov Re: TLE #62 [2] // Problem 1589. Sokoban 30 Apr 2011 23:13

I have TLE 62 too. Don't have ideas of how to proceed.
Can you give a hint of how you have improved you program to pass this test?

Oracle[Lviv NU] Re: TLE #62 [1] // Problem 1589. Sokoban 19 May 2011 02:05

I've stored only those positions, which can not be processed in some steps by greedy algo + store only positions, where man is in lowest-left cell + stop, when position is surely bad (I've used a lot of classes of bad positions) + make moves, that is surely necessary.

adityarev Re: TLE #62 // Problem 1589. Sokoban 6 Jun 2019 05:54

Hi Oracle, can u give us some cases that considered as a bad position? I have a prunning issue also on my solution

Discussion of Problem 1589. Sokoban