Here is the problem statement
http://www.spoj.com/problems/SHOP/
I suggest a way which is not fast enough( you won't be the first in the best solutions field :) ) but works great. This is done by a simple BFS ( you can find information about BFS here) but in a different way (without queue). Initially we keep an array which we will call ans (the array of answers) and the field ans[x][y] will show the minimum cost of getting to the point (x,y) . Initially all the elements are equal to infinity ( to a very larg number which we will call INF). We give our start point the value of 0. Then we loop over our array N*M times ( this is the worst case) and every time we loop we check if the current point we are on is not equal to INF we check its neighbours and update the value if necessary. Then we output the value of ans[x2][y2] where (x2,y2) is the destination point).
http://www.spoj.com/problems/SHOP/
I suggest a way which is not fast enough( you won't be the first in the best solutions field :) ) but works great. This is done by a simple BFS ( you can find information about BFS here) but in a different way (without queue). Initially we keep an array which we will call ans (the array of answers) and the field ans[x][y] will show the minimum cost of getting to the point (x,y) . Initially all the elements are equal to infinity ( to a very larg number which we will call INF). We give our start point the value of 0. Then we loop over our array N*M times ( this is the worst case) and every time we loop we check if the current point we are on is not equal to INF we check its neighbours and update the value if necessary. Then we output the value of ans[x2][y2] where (x2,y2) is the destination point).
No comments:
Post a Comment