Period 3 2D Arrays Pt 2 - Sample Problem 2

Sample Problem 2 - Competition!

For this problem, please listen to instructions. There will be an in-class competition which will be an opportunity for extra credit. However, you must complete this problem either way as part of the homework.

Problem

This question involves a path through a two-dimensional (2D) array of integers, where the path is based on the values of elements in the array. When an element of the 2D array is accessed, the first index is used to specify the row and the second index is used to specify the column. The following Location class represents a row and column position in the 2D array.

// Run this code cell so that using the location class doesn't throw errors in future code cells!
public class Location {
    private int theRow;
    private int theCol;

    public Location(int r, int c) {
        theRow = r;
        theCol = c;
    }

    public int getRow() {
        return theRow;
    }

    public int getCol() {
        return theCol;
    }
}

The following GridPath class (see the next code cell) contains the 2D array and methods to use to determine a path through the array. You will write two methods of the GridPath class.

(a) Write the getNextLoc method, which returns a Location object that represents the smaller of two neighbors of the grid element at row and col, according to the following rules.

• The two neighbors that are considered are the element below the given element and the element to the right of the given element, if they exist.
• If both neighbors exist, the Location of the neighbor with the smaller value is returned. Two neighbors will always have different values.
• If only one neighbor exists, the Location of the existing neighbor is returned.

For example, assume that the grid contains the following values:

The following table shows some sample calls to getNextLoc.

Method Call	Explanation
getNextLoc(0, 0)	Returns the neighbor to the right (the Location representing the element at row 0 and column 1), since 3 < 11
getNextLoc(1, 3)	Returns the neighbor below (the Location representing the element at row 2 and column 3), since 15 < 16
getNextLoc(2, 4)	Returns the neighbor below (the Location representing the element at row 3 and column 4), since the given element has no neighbor to the right
getNextLoc(4, 3)	Returns the neighbor to the right (the Location representing the element at row 4 and column 4), since the given element has no neighbor below

In the example, the getNextLoc method will never be called with row 4 and column 4, as those values would violate the precondition of the method.

(b) Write the sumPath method, which returns the sum of all values on a path in grid. The path begins with the element at row and col and is determined by successive calls to getNextLoc. The path ends when the element in the last row and the last column of grid is reached. For example, consider the following contents of grid. The shaded elements of grid represent the values on the path that results from the method call sumPath(1, 1). The method call returns 19 because 3 + 1 + 2 + 1 + 9 + 1 + 4 + 1 + 0 + 1 + 1 + 5 = 19.

public class GridPath {
    private int[][] grid;
    // Constructor
    public GridPath(int[][] values) {
        grid = values;
    }
    // Determines the next location to move to
    public Location getNextLoc(int row, int col) {
        boolean hasBelow = row + 1 < grid.length; // Check if there's a row below
        boolean hasRight = col + 1 < grid[0].length; // Check if there's a column to the right
        if (hasBelow && hasRight) {
            // Choose the smaller value between the cell below and the cell to the right
            if (grid[row + 1][col] < grid[row][col + 1]) {
                return new Location(row + 1, col);
            } else {
                return new Location(row, col + 1);
            }
        } else if (hasBelow) {
            // Move down if only the cell below exists
            return new Location(row + 1, col);
        } else if (hasRight) {
            // Move right if only the cell to the right exists
            return new Location(row, col + 1);
        } else {
            // No movement possible (this is the last cell)
            return null;
        }
    }
    // Calculates the sum of the path from the start to the bottom-right corner
    public int sumPath(int row, int col) {
        int sum = grid[row][col]; // Start with the value of the initial cell
        // Continue until the bottom-right corner is reached
        while (row != grid.length - 1 || col != grid[0].length - 1) {
            Location nextLoc = getNextLoc(row, col);
            if (nextLoc == null) {
                break; // This handles edge cases gracefully
            }
            row = nextLoc.getRow();
            col = nextLoc.getCol();
            sum += grid[row][col]; // Add the value of the next cell
        }
        return sum;
    }
}
// Assuming this is the Location class
class Location {
    private int row;
    private int col;
    public Location(int row, int col) {
        this.row = row;
        this.col = col;
    }
    public int getRow() {
        return row;
    }
    public int getCol() {
        return col;
    }
}