catchclrs
BAN USERCoding owl's suggestions is the best.. try providing a readable algorithm. even a monkey can write a peice of code. Having said that, I again have to agree with coding owl, DP is the only approach "I" can think of:
1. create a matrix with n*m column for every element in the matrix
2. the number of rows will be the number k from the question
3. start making entries: for every entry do the following
a) for first row:
1. compute values from all possible directions.
2.store the max product and the direction u pick
b) for rows other than first row:
1. compute values from direction indicated in previous step. if its up/down, u can check only for biggest of two values, go up or down etc
2.store the max product and the direction u pick
so if u have already computed a value, u can reuse. If any one can make it better please post you answers
the question is somewhat flawed. if you dont have to recompute the danger value, then how can u assure the danger value is right as the graph is built
- catchclrs June 14, 2015