Method Signature

int longestPath(List<String> grid)

• grid represents the 2D grid using a 1D list of strings.
• Each string represents one row.
• Within each row string, values are separated by commas.
• 0 means the cell is empty and can be used in the path.
• 1 means the cell is a wall and cannot be used in the path.
• Returns the maximum number of cells in a valid path from the first row to the last row.
• Returns 0 if no such path exists.

Constraints

• 1 ≤ grid.size() ≤ 10
• 1 ≤ number of values in each row ≤ 10
• 1 ≤ grid.size() * number of values in each row ≤ 30
• Each value is either 0 or 1.
• All rows contain the same number of comma-separated values.
• You may move only one cell at a time in the four directions: up, down, left, or right.
• The path must start in the first row and end in the last row.
• A cell cannot be used more than once in the same path.

Notes

• You may start from any empty cell in the first row.
• You may end at any empty cell in the last row.
• The path length is measured as the number of cells included in the path.

Examples

Example 1

• longestPath(grid = ["0,0,0", "1,0,1", "0,0,0"])
• Output: 5
• One longest valid path is through the middle column and then across the last row.

Example 2

• longestPath(grid = ["0,1,0", "0,1,0", "0,0,0"])
• Output: 5
• A longest valid path can start at the top-left cell and reach the last row without revisiting any cell.

Example 3

• longestPath(grid = ["1,1,1", "0,0,0", "0,0,0"])
• Output: 0
• There is no empty cell in the first row, so no valid path can start.

Example 4

• longestPath(grid = ["0", "0", "0"])
• Output: 3
• The only valid path uses all three cells from top to bottom.