2024 AP CSA FRQ 4 Solution – GridPath 2D Arrays

2024 AP CSA FRQ 4 – GridPath (Solution)

This solution shows how to implement getNextLoc and sumPath in the GridPath class using a 2D int[][] array and the provided Location class.

Given Location Class (for reference)

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;
    }
}

Part (a) – getNextLoc

Goal: From position (row, col), return the neighbor with the smaller value among:

  • The element directly below: (row + 1, col), if it exists.
  • The element directly to the right: (row, col + 1), if it exists.

If only one neighbor exists (bottom row or rightmost column), return that neighbor.

public Location getNextLoc(int row, int col)
{
    int numRows = grid.length;
    int numCols = grid[0].length;

    boolean hasBelow = (row + 1 < numRows);
    boolean hasRight = (col + 1 < numCols);

    if (hasBelow && hasRight)
    {
        // Both neighbors exist: choose the one with the smaller value
        int belowValue = grid[row + 1][col];
        int rightValue = grid[row][col + 1];

        if (belowValue < rightValue)
        {
            return new Location(row + 1, col);
        }
        else
        {
            return new Location(row, col + 1);
        }
    }
    else if (hasBelow)
    {
        // Only below exists
        return new Location(row + 1, col);
    }
    else
    {
        // Only right exists
        return new Location(row, col + 1);
    }
}

Why this earns full credit:

  • Checks for existence of neighbors using row/column bounds.
  • Correctly compares the values in grid to decide which Location to return.
  • Handles all three cases: both neighbors, only below, only right.
  • Uses the provided Location constructor correctly.

Part (b) – sumPath

Goal: Starting at (row, col), follow the path determined by repeated calls to getNextLoc until you reach the bottom-right element of grid, and return the sum of all values along the path (including the starting and ending positions).

The path ends at (numRows - 1, numCols - 1). At each step, we:
1) Add the current grid value to the sum. 2) Move to the next Location from getNextLoc.
public int sumPath(int row, int col)
{
    int numRows = grid.length;
    int numCols = grid[0].length;

    int sum = 0;

    // Always include the starting location
    int currentRow = row;
    int currentCol = col;

    while (true)
    {
        sum += grid[currentRow][currentCol];

        // If we have reached the bottom-right cell, we are done
        if (currentRow == numRows - 1 && currentCol == numCols - 1)
        {
            break;
        }

        // Move to the next location on the path
        Location next = getNextLoc(currentRow, currentCol);
        currentRow = next.getRow();
        currentCol = next.getCol();
    }

    return sum;
}

Why this earns full credit:

  • Uses getNextLoc as required (does not re-implement its logic).
  • Correct stopping condition when reaching the last row and last column.
  • Includes both the starting and ending grid values in the sum.
  • Works for any valid starting cell that is not already the bottom-right element.
Common mistakes: forgetting to add the starting or ending value to the sum, or writing a loop condition that might skip the last cell or never terminate if getNextLoc is not used properly.

Contact form