Computer Science A

Course Progress 0/0
Sprint View
Week 19 2024 FRQ 4

2024 FRQ 4

4 min read

Question 4: GridPath - 2D Array Path Navigation

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.

Code Runner Challenge

The Location class represents a row and column position in a 2D array.

Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

The following GridPath class contains the 2D array and methods to use to determine a path through the array. You will write two methods of the GridPath class.

Code Runner Challenge

The GridPath class contains a 2D array and methods to determine a path through the array.

Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

(a) Write the getNextLoc method

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 grid contains the following values:

  0 1 2 3 4
0 12 3 4 13 5
1 11 21 2 14 16
2 7 8 9 15 0
3 10 17 20 19 1
4 18 22 30 25 6

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.

Complete the getNextLoc method:

Code Runner Challenge

Complete the getNextLoc method according to the rules above. The method should return a Location representing the smaller neighbor (either below or to the right).

Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

(b) Write the sumPath method

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 + 2 + 9 + 4 + 0 + 1 = 19.

  0 1 2 3 4
0 12 30 40 25 5
1 11 3 22 15 43
2 7 2 9 4 0
3 8 33 18 6 1

Write the sumPath method. Assume getNextLoc works as intended, regardless of what you wrote in part (a). You must use getNextLoc appropriately in order to receive full credit.

Code Runner Challenge

Complete the sumPath method. It should return the sum of all values on a path through grid, starting at the given row and col, using successive calls to getNextLoc until reaching the last row and last column.

Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Class information for this question:

public class Location
    private int theRow
    private int theCol
    public Location(int r, int c)
    public int getRow()
    public int getCol()

public class GridPath
    private int[][] grid
    public Location getNextLoc(int row, int col)
    public int sumPath(int row, int col)

Course Timeline