Here is the problem statement
http://www.spoj.com/problems/ACPC10D/
This task can be solved with creating a graph out of our array and use BFS to solve it but there is a better way. We can use dynamic programming to solve this. Create an 2 dimensional array. Let's name that array b.
b[i][j] will show the minimum number of points we will have to collect in order to reach i-th row and j-th column. We now that b[1][1]=a[1][1]. Now we can just loop over our input array and for every element a[i][j] we update the value of b[i+1][j],b[i+1][j+1],b[i][j+1]. (All the values of array b equal to infinty from the beginning).
http://www.spoj.com/problems/ACPC10D/
This task can be solved with creating a graph out of our array and use BFS to solve it but there is a better way. We can use dynamic programming to solve this. Create an 2 dimensional array. Let's name that array b.
b[i][j] will show the minimum number of points we will have to collect in order to reach i-th row and j-th column. We now that b[1][1]=a[1][1]. Now we can just loop over our input array and for every element a[i][j] we update the value of b[i+1][j],b[i+1][j+1],b[i][j+1]. (All the values of array b equal to infinty from the beginning).
No comments:
Post a Comment