We have a maze R X C where 1<=R,C<=500. This maze is filled by numbers from -1 to 100. Now , the game is as follows :
- Where ever there is -1 in square , assume that is a stone block in that cell and you cannot move throught that cell.
- You can begin from any cell on 1st column (of course that does not have -1) and exit from any cell from last column .
- You can move either up , down , right.
- As you move , u collect the numbers in the cell except -1 which denote a big stone is placed in our maze. Each cell has to be visited once only.
What is the path from left to right where you can select maximum sum of numbers ? EASY !! Dp can do magic But But ... here's the catch — Rule 5 .
- We can move out of maze if we can reach first or bottom row. But then 2 things happen :
a) We lose all points collected till now. b) we renter the maze in the same column but in the opposite cell.
ex: consider 3X3 maze (1 -indexed) . so if we reach say , (1,2) we can exit from there and lose all points and enter (3,2) , and game continues ....
Now what will the path with maximum points ?
My approach was to first find all possible source points. If we come out of maze form 1st or last row , we begin fresh and where we land next becomes our source point. So , I perform multi source BFS taking cells of leftmost column to get it . And do calculate such optimal path score for each cell by dp . IS there any other optimal method to solve this game ?
