A map is provided as gray level image in raw format (available below) and the value at a point (pixel) is its height information. From a point, one can only travel in horizontal or vertical direction (edge) to its adjacent point. The cost of a horizontal or vertical shift between two adjacent points is their height difference, which corresponds to energy spent on the movement, e.g., cost(a, b) =1+|map(a)-map(b)| for adjacent points a and b. Compute the shortest path starting from top left corner point (0, 0) to all other points by using the greedy algorithm. The cost of a path is the sum of edge costs in horizontal and vertical directions.
Input Map: a 2D array in row based order. It has W*H = 250*200 dots(points).
Value at a position in the map: 1byte character (8bits) for height value, i.e., the height value ranges from 0 to 255.
(1) A grey level image to show the final direction to reach every point in the map. In detail, the value at each point shows the direction from its previous position to it on the shortest path. For example, at a point, you can use a number from 50, 100, 150, 200 to represent a direction among N(↑),E(→),S(↓),W(←).
(2) Mark a path in another image file.
(3) A txt file to display a value at each point that is the shortest path cost to the point.(For this one, as each node will take a sum, which the value near right down corner will be far greater then 255, so you can output this one as txt file and save the actual number)
(4) Improvement: efforts to speed up the computation and reduce the memory are encouraged. For example, you can use additional arrays as the working space to register immediate values, use separate data structures such as link list, queue, and heap to reduce the computation complexity.
[url removed, login to view] for input
You can use [url removed, login to view] or start from scratch.
2 sample file output.
In [url removed, login to view], the path is marked as 255, this file shows the path.
In [url removed, login to view], the numbers represent the directions. 50 means ↑, 100 means →, 150 means ↓, 200 means ←
Please demonstrate you understand project when bidding to save both of us time. Thanks.
11 freelancers are bidding on average $138 for this job
Hi I have 2+ years experience working with similar skills, I can get the task done for you, so if you are interested in a collaboration please contact me..... With warm regards
Hi, I have 10+ year experience. I will utilize greedy approach, this will result into usual Dijkstra algorithm. I will provide you complete implementation within 2 days. Thanks, Anurag
Hi, I'm an experienced C++ programmer and I know algorithms very well. I can implement Dijkstra algorithm in order to find the shortest path in the map you provide.