Maximum Path Sum in a Grid with Specific Movement Constraints

Problem Statement

Maximum Path Sum in a Grid with Specific Movement Constraints Problem Description Find the path that maximizes the score when traversing a rectangular grid under specific movement constraints. You start in either the top row of the grid, column p , and move down, or the bottom row, column q , and move up. You must visit exactly one cell per row. The score is the sum of all integer values in the cells visited. You can only move to adjacent cells (including diagonals) in the next row. All moves must stay within the boundaries of the board. Examples Example 1: Input: board = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] p = 1 q = 0 Explanation: For a 3x3 grid, the cursor starts at position (0, p) = (0, 1) or (rows - 1, q) = (2, 0). Path 1 (starting at (0,1) and moving down): Grid: 0 1 2 ----- 1 2 3 <- (0,1) value 2 4 5 6 <- (1,2) value 6 7 8 9 <- (2,2) value 9 Path: (0,1) -> (1,2) -> (2,2) Maximum score = 2 + 6 + 9 = 17 Path 2 (starting at (2,0) and moving up): Grid: 0 1 2 ----- 1 2 3 <-