10021 - Cube in the labirint

[Mohammad Mahmudur Rahman]

Hi, I am trying to solve this problem. I can easlily find the shortest distance between the given cells in the lybirinth using BFS, but I am not sure what is the exact way to ensure that the cube will lay on the same side on both the starting & target points. I modified BFS to do this but finding that my program is not giving the shortest path for some test cases. Can someone give me a brief idea how to do it? Thanks in advance.

[matrix2]

Hi...
I can tell you that moving the cube on the board may be simulated. For the algo, I think a BFS is the solution

[shanto86]

for those who will get WA a case:

Code: Select all

1

3 3
1 1
3 3
h
3 1
v
1 3

answer is 12.