#include #include #include #include #include using namespace std; class Solution { private: int rows; int cols; vector> grid; // dpMax[i][j]: max expression value for valid expressions that END at digit cell (i,j). // Only meaningful for digit cells. vector> dpMax; vector> computed; void compute(int r, int c) { if (computed[r][c]) { return; } computed[r][c] = true; int digitVal = grid[r][c] - '0'; int bestMax = digitVal; // look at cells that can reach (r,c) via an operator // an operator at (r-1,c) or (r,c-1) could connect to a digit before it vector> opDirs = {{-1, 0}, {0, -1}}; for (auto& d : opDirs) { int opR = r + d[0]; int opC = c + d[1]; if (opR < 0 || opC < 0) { continue; } if (isdigit(grid[opR][opC])) { continue; } char op = grid[opR][opC]; // the operator at (opR,opC) must be reached from a digit cell vector> digitDirs = {{-1, 0}, {0, -1}}; for (auto& dd : digitDirs) { int prevR = opR + dd[0]; int prevC = opC + dd[1]; if (prevR < 0 || prevC < 0) { continue; } if (!isdigit(grid[prevR][prevC])) { continue; } compute(prevR, prevC); if (op == '+') { bestMax = max(bestMax, dpMax[prevR][prevC] + digitVal); } else { bestMax = max(bestMax, dpMax[prevR][prevC] - digitVal); } } } dpMax[r][c] = bestMax; } public: int maxValidExpressionPath(vector> matrix) { grid = matrix; rows = matrix.size(); cols = matrix[0].size(); dpMax = vector>(rows, vector(cols)); computed = vector>(rows, vector(cols, false)); int result = INT_MIN; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (isdigit(grid[i][j])) { compute(i, j); result = max(result, dpMax[i][j]); } } } return result; } };

AI Assistant