Be sure to include: Algorithm description ( paragraph or pseudo code) Proof that

Question

Be sure to include: Algorithm description ( paragraph or pseudo code) Proof that your algorithm is correct Analysis of the run time of your algorithm 3. Rocky Mountain High Suppose you are given o nxn matrix A of positive numbers representing an elevation map of a region. Suppose you want to travel from the leftmost side of the grid to the right most side of the grid (starting at any leftmost location and ending at any rightmost location). Furthermore, you may only move 1 square at a time from either left to right, or diagonally up-right, or diagonally down-right. The cost of each move is the absolute value difference between the numbers (elevations) between the two positions you move between. Design an O(n 2) time olgorithm to compute the cost of the shortest route across the map. Partial credit will be given for slightly slower solutions.

Explanation / Answer

import java.util.Arraylist; public class PrintPath { static ArrayList paths = new ArrayList(); public static long getUnique(int m, int n, int i, int j, String pathlist) { pathlist += ("(" + i + ", " + (j) + ") => "); if(m == i && n == j) { paths.add(pathlist); } if( i > m || j > n) { return 0; } return getUnique(m, n, i+1, j, pathlist)+getUnique(m, n, i, j+1, pathlist); } public static void printPaths() { int count = 1; System.out.println("There are "+paths.size() + " unique paths: "); for (int i = paths.size()-1; i>=0; i--) { System.out.println( "path " + count + ": " + paths.get(i)); count++; }

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.