GridPath is #4 from the from the 2024 AP Computer Science A Free Response problems.

https://apcentral.collegeboard.org/media/pdf/ap24-frq-comp-sci-a.pdf

Part (a) getNextLoc method

public Location getNextLoc(int row, int col)
{
    Location belowLoc = new Location(row + 1, col);
    Location rightLoc = new Location(row, col + 1);
    
    if(row == grid.length - 1)
        return rightLoc;
    
    if(col == grid[0].length - 1)
        return belowLoc;
    
    if(grid[row + 1][col] < grid[row][col + 1])
        return belowLoc;
    else
        return rightLoc;
}

This is a revised solution. My original getNextLoc solution contained a subtle error.

Part (b) sumPath method

public int sumPath(int row, int col)
{
    int sum = grid[row][col];
    Location loc = getNextLoc(row, col);
    
    while(loc != null)
    {
        sum += grid[loc.getRow()][loc.getCol()];
        
        if(loc.getRow() < grid.length - 1 ||
                loc.getCol() < grid[0].length - 1)
            loc = getNextLoc(loc.getRow(), loc.getCol());
        else
            loc = null;
    }
    
    return sum;
}

Java files with test code

FourTest.java includes JUnit 5 test code with the examples from the problem. See Running JUnit 5 tests. Location.java includes working equals, toString, and hashCode methods.

Location.java
GridPath.java
FourTest.java

2024 AP CS Exam Free Response Solutions

Help & comments

Get help from AP CS Tutor Brandon Horn

See an error? Question? Please comment below.

Comment on GridPath

2024-05-13 comment

Ray Stuckey

What about doing part b recursively?
** spoilers below**
Something like this

public int sumPath(int row, int col) {
    //part b
    if (grid[0].length - 1 == col && grid.length - 1 == row) {
        return grid[row][col];
    }
    Location next = getNextLoc(row, col);
    return grid[row][col] + sumPath(next.getRow(), next.getCol());
}

Response

Yes. This works.

I didn’t post a recursive solution since I didn’t personally see it adding anything, but I could certainly see it being more intuitive for others.

2024-05-17 comment

Mike Crudele, APCS Teacher at Doral Academy

//my recursive solution:   
public int sumPathRec(int row, int col) {
    if (row == grid.length-1 && col == grid[0].length-1) {
        return grid[row][col];
    }
    else {
        Location loc = getNextLoc(row, col);
        int nextRow = loc.getRow();
        int nextCol = loc.getCol();
        return grid[row][col] + sumPath(nextRow, nextCol); 
    }
}

Response

Yep. This works. Thanks for sharing.