| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1206 | PA - Ice Arena |
|
| 1207 | PB - The Balloon Kingdom |
|
| 1208 | PC - Ant |
|
| 1209 | PD - Keys |
|
| 1210 | PE - Biased Grade |
|
| 1211 | PF - Crimiville |
|
Description
Citizens of the ice kingdom plan to build an ice arena, which is a rectangular area of N x M ice grids. However, they find that the original heights of the ice cubes on the grids are not equal, and given the time constraints it is difficult for them to modify the original height too much. Thus, only one of the three possible actions can be taken on the ice cube for each grid: digging it (decreasing its height by 1), filling it (increasing its height by 1), or doing nothing.
After taking one and only one action for each grid, the citizens choose grids with the same modified height for ice skating to prevent getting hurt on an uneven surface, and place barriers on the grids that are not chosen.
To form a safe area for ice skating , the citizens hope to use the chosen grids that are connected through vertical or horizontal walks. Please find the maximum possible safe area, that is, the maximum number of chosen grids that are connected.
Input
The first line of input data contains an integer T(1 <= T <= 1000) specifying the number of the cases.
The first line of each test case contains two integers N and M (1<=N, M<=100) indicating the dimensions of the ice arena. Each of the next N lines contains M integers H (1<=H<=10000) denoting the original height of each gird.
Output
For each test case, display a single line containing the maximum number of chosen grids (after taking the actions) that are connected.
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)