Matrix Land : week of code 35 (Hackerrank)

hey can anyone share their approach for this problem !!

question link : Programming Problems and Competitions :: HackerRank

@ vijju123

2 Likes

My approach was to make a DP of [3][3][n][m]… which will represent (direction it will go, direction from where it is coming, x, y).

Now there can be 3 major cases:

  1. Going down: 3 sub-cases of this are: last direction was right, left or down. Depending on this you will call next part.
  2. Going right: 2 sub-cases of this are: coming from up or from left to right. (right to right doesn’t make sense)
  3. Going left: 2 subcases of this are: coming from up of right to left.

Solution now will be to call DP in first row for all cases. O(33nm) = maximum (0.3610^8)
This solution is correct. I don’t know why i got abort called on 2 of the cases but otherwise it’s one of the correct approaches.

2 Likes

great work mate !! can u plzz share your code

Programming Problems and Competitions :: HackerRank … Is it visible to you? Now it works for all the test cases too… I changed DP to [3][3][2][m], this works as we only need next for calculation of current row. Earlier due to size of [3][3][n][m] it was giving abort.

yeah i am able to see your code
thnks man!!