To solve this problem, we need to determine if we can make all elements of a 2D grid zero using a specific operation: choosing two adjacent cells and subtracting 1 from both.
Approach
- Initial Check: Ensure all cells have non-negative values. If any cell is negative, it's impossible to make it zero using the allowed operation (since we can only subtract values).
- Process Rows: For each row except the last one, eliminate the value of each cell by moving the value down to the cell directly below it. This is because the only way to adjust the value of a cell in a non-last row is to use the down operation (since the right operation will be handled later).
- Process Last Row: After processing all non-last rows, the last row can only be adjusted using the right operation. Eliminate the value of each cell in the last row by moving it to the right.
- Final Check: If the last cell in the grid is zero after all operations, the answer is possible; otherwise, it's not.
Solution Code
def can_make_zero(grid):
n = len(grid)
if n == 0:
return True
m = len(grid[0])
# Make a copy to avoid modifying original grid
g = [row.copy() for row in grid]
# Check initial non-negative
for row in g:
for num in row:
if num < 0:
return False
# Process all rows except last
for i in range(n-1):
for j in range(m):
val = g[i][j]
if val < 0:
return False
# Apply down operations
g[i][j] -= val
g[i+1][j] -= val
if g[i+1][j] < 0:
return False
# Process last row
for j in range(m-1):
val = g[-1][j]
if val < 0:
return False
# Apply right operations
g[-1][j] -= val
g[-1][j+1] -= val
if g[-1][j+1] < 0:
return False
# Check last cell
return g[-1][-1] == 0
# Example usage:
# grid = [[1,1],[1,1]] → returns True
# grid = [[2,3,2]] → returns False
# grid = [[0]] → returns True
Explanation
- Initial Check: We first ensure no cell starts with a negative value since we can't add to cells to make them zero.
- Row Processing: For each cell in non-last rows, we move its value down to the cell below. This sets the current cell to zero and adjusts the cell below.
- Last Row Processing: For the last row, we move each cell's value to the right, setting the current cell to zero and adjusting the next cell to the right.
- Final Check: The last cell in the grid must be zero for the solution to be valid, as there are no more operations left to adjust it.
This approach efficiently processes the grid in O(nm) time complexity, which is optimal for this problem. The space complexity is O(nm) due to the copy of the grid, but we can modify the original grid to reduce it to O(1) if allowed. However, using a copy ensures we don't alter the input data.


作者声明:本文包含人工智能生成内容。