You are given an m x n matrix grid of positive integers. Your task is to determine if it is possible to make either one horizontal or one vertical cut on the grid such that:
Each of the two resulting sections formed by the cut is non-empty.
The sum of elements in both sections is equal , or can be made equal by discounting at most one single cell in total (from either section).
If a cell is discounted, the rest of the section must remain connected.
Return true if such a partition exists; otherwise, return false.
Note: A section is connected if every cell in it can be reached from any other cell by moving up, down, left, or right through other cells in the section.
Input: grid =[[1,4],[2,3]]Output: trueExplanation:

* A horizontal cut after the first row gives sums `1 + 4 = 5` and `2 + 3 = 5`, which are equal. Thus, the answer is`true`.
Input: grid =[[1,2],[3,4]]Output: trueExplanation:
* A vertical cut after the first column gives sums `1 + 3 = 4` and `2 + 4 = 6`.* By discounting 2 from the right section(`6 - 2 = 4`), both sections have equal sums and remain connected. Thus, the answer is`true`.
Input: grid =[[1,2,4],[2,3,5]]Output: falseExplanation:
***** A horizontal cut after the first row gives `1 + 2 + 4 = 7` and `2 + 3 + 5 = 10`.* By discounting 3 from the bottom section(`10 - 3 = 7`), both sections have equal sums, but they do not remain connected as it splits the bottom section into two parts(`[2]` and `[5]`). Thus, the answer is`false`.
We want to split the grid into two non-empty parts with a single horizontal or vertical cut, such that the sums are equal or can be made equal by discounting at most one cell (removing its value from one part), and the remaining section must stay connected. For each possible cut, check if the sums are equal, or if the difference can be matched by removing a border cell (which keeps the section connected).
For each possible horizontal cut (between row i and i+1):
Compute the sum of the top and bottom parts.
If equal, return true.
If not, check if the difference can be matched by removing a cell from the border row (last row of top or first row of bottom), and the section remains connected.
For each possible vertical cut (between column j and j+1):
Compute the sum of the left and right parts.
If equal, return true.
If not, check if the difference can be matched by removing a cell from the border column (last col of left or first col of right), and the section remains connected.
classSolution:
defisPossibleToCutGrid(self, grid: list[list[int]]) -> bool:
m, n = len(grid), len(grid[0])
total = sum(sum(row) for row in grid)
# Horizontal cuts top_sum =0for i in range(m -1):
top_sum += sum(grid[i])
bot_sum = total - top_sum
if top_sum == bot_sum:
returnTrue diff = abs(top_sum - bot_sum)
# Try discounting a cell on the borderif top_sum > bot_sum:
# Remove from last row of topfor v in grid[i]:
if top_sum - v == bot_sum:
returnTrueelse:
# Remove from first row of bottomfor v in grid[i+1]:
if bot_sum - v == top_sum:
returnTrue# Vertical cuts left_sum = [0] * n
for j in range(n -1):
for i in range(m):
left_sum[j] += grid[i][j]
right_sum = sum(grid[i][j+1] for i in range(m))
lsum = sum(left_sum[:j+1])
rsum = total - lsum
if lsum == rsum:
returnTrue diff = abs(lsum - rsum)
# Try discounting a cell on the borderif lsum > rsum:
for i in range(m):
if lsum - grid[i][j] == rsum:
returnTrueelse:
for i in range(m):
if rsum - grid[i][j+1] == lsum:
returnTruereturnFalse