Many thank to Oracle[Lviv NU]. His test data helped me a lot. But now my program solves all that tests as well as any test that I can imagine.
Can anyone give test cases that he consider to be hard.

Thanks!

I've found one test that takes about 20 seconds to process. It looks quite simple but for my greedy approach it's real hell

########
#......#
#------#
#*****-#
#------#
#$$$$$$#
#-----@#
########

Now it takes about 3 seconds to process this test but still TL 57-62...

Other not bad test:
########
#.....-#
#--##--#
#-*----#
#--#-#-#
#$$$$$$#
#-----+#
########

Edited by author 01.05.2011 00:06

Edited by author 01.05.2011 02:34

It looks hardly possible to pass this problem in Java.
I have really good solution but depending on configuration I always get TL 56,57 or 62.
Maybe I've missed cool truncation?
I store situation in one long variable in bit representation. In this case it's easy to check if all blocks are on their places (just do binary &)
Also I use 3 different heuristics to filter deadlock situations (Block with unreachable destination, stuck block not on destination, strongly connected area without man inside and with amount of blocks greater then amount of destinations)  Also I use priority queue and process turns wich moves blocks closer to closest unblocked destination than it was in previous turn. I turn off heuristics automatically if they are not effective in current situation. (it looks effective on some tests but it doesn't actually help to pass 62 :D )
I'm pretty sure that even simpler C++ solution can pass all tests.
Java, Java, why you are so slow?...
Time limit is too strict.
Admins, is it good idea to add this problem to list of problems that one can have problem with using Java?
Guys...
If you have good ideas of how to improve don't hesitate to write them here.

Thanks,

Vitaliy

Edited by author 01.05.2011 02:31

My method needs a plenty of memory to store information, although got a Memory Limit Exceeds, but it can give out a solution to all the hard data in discuss in less than 0.1s. however, I still found some data that make my program run very slow(up to 2s), and even can not provide a solution(the solution exists).

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


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


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


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

can any one who passed this problem share some more outstanding ideas about how to optimize the algorithm?

 ######
##  . #
# * # #
# .$  #
#  #$##
## @ #
 #####

my personal favorites:
########
##.* $.#
#  * . #
#   *. #
## $.$ #
# $*$$$#
#..   @#
########

and next is hard only if you don't use any estimate func:
########
#.     #
#$ $ $ #
#@ $ $ #
#  $ $ #
#  ****#
#......#
########

Edited by author 17.08.2018 15:25