Trapped Water in a Grid

You are given an \(n \times m\) grid where each cell represents the height of a building. When it rains, water can be trapped between the buildings. Your task is to compute the maximum amount of water that can be trapped over the grid.

The water trapped at a cell \((i,j)\) is determined by the formula:

\(\text{water}(i,j) = \max(0, \min(L_{i,j}, R_{i,j}, T_{i,j}, B_{i,j}) - H_{i,j})\)

where:

• \(L_{i,j}\) is the maximum height to the left of cell \((i,j)\) (including the cell itself),
• \(R_{i,j}\) is the maximum height to the right,
• \(T_{i,j}\) is the maximum height above,
• \(B_{i,j}\) is the maximum height below,
• \(H_{i,j}\) is the height at cell \((i,j)\).

If \(n < 3\) or \(m < 3\), no water can be trapped.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case starts with a line containing two integers \(n\) and \(m\) representing the dimensions of the grid. This is followed by \(n\) lines, each containing \(m\) space-separated integers that denote the grid values.

outputFormat

For each test case, output a single integer that represents the maximum amount of water that can be trapped, each on a new line.

1
2 2
1 1
1 1

0