Discussion @ 1016. Cube on the Walk @ Timus Online Judge

Help, please! How to solve this problem? Any hits, please (+)

Posted by Victor Barinov (TNU) 2 Feb 2005 20:52

Hello, everybody!

I tryed to solve this problem for a week. I DO NOT KNOW WHAT TO DO. I can't think out anything :(

Thanks.

Re: Help, please! How to solve this problem? Any hits, please (+)

Posted by Yaroslavtsev Grigory (SpbSPU) 2 Feb 2005 21:12

Dijkstra, Dijkstra... You can make a graph, where every vertex defines a state of the cube (I mean position and rotation) and every edge defines how much does it cost to move from one position to the other, then use Dijkstra, Bellman or whatever you want. I think it will help.

Edited by author 02.02.2005 21:21

Thank you very much! I got AC! (-)

Posted by Aleksey Meshnikovsky 3 Feb 2005 16:20

I got Accepted. Thanks to Yaroslavtsev Grigory (SpbSPU)! (-)

Posted by Victor Barinov (TNU) 3 Feb 2005 19:04

Re: I got Accepted. Thanks to Yaroslavtsev Grigory (SpbSPU)! (-)

Posted by PSV 2 Jan 2007 00:28

I think BFS is useable too!

Re: I got Accepted. Thanks to Yaroslavtsev Grigory (SpbSPU)! (-)

Posted by SkorKNURE 13 Jul 2008 05:18

I think you can write that iff you have already accepted your solution.

about BFS

Posted by JTim 16 Jan 2011 22:06

I think you can use BFS if numbers on top, bottom, left, right, front and back sides of cube are equal, else Dijkstra or bruteforce :)

Discussion of Problem 1016. Cube on the Walk