http://www.spoj.com/problems/TRIKA/
We will solve this task using dynamic programming. Let us have an array A where A[i][j] shows the maximum points we will have left for reaching the cell (i,j). Initially all the elements of array A are equal to -1 which means that we haven't visited it yet. Our starting point will be equal to the value we have form the beginning. Then we need to loop over array maximum N*M times and whenever we find a spot which is not -1 we check all it's neighbors and update the values of array A. Check the source code for a better understanding.
We will solve this task using dynamic programming. Let us have an array A where A[i][j] shows the maximum points we will have left for reaching the cell (i,j). Initially all the elements of array A are equal to -1 which means that we haven't visited it yet. Our starting point will be equal to the value we have form the beginning. Then we need to loop over array maximum N*M times and whenever we find a spot which is not -1 we check all it's neighbors and update the values of array A. Check the source code for a better understanding.
No comments:
Post a Comment