In the square binary grid, land cells contain 1 and water cells contain 0. An island consists of land cells connected through shared edges, using up, down, left, or right moves. You may turn at most one water cell into land. Return the largest possible island area, measured in cells, after that optional change. Diagonal contact alone does not connect islands.
Example 1:
Input: grid = [[0,0],[0,0]]
Output: 1Explanation: Turn any one water cell into land. It forms a single-cell island, so the largest area is 1.
Example 2:
Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9Explanation: Turning the center cell into land joins the surrounding eight cells into an island of area 9. Those surrounding cells already belong to one island and are counted only once.
Example 3:
Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 3Explanation: Change the top-middle cell to land to connect the two top corners, forming an island of area 3. No single change can connect three or four corners.
Constraints:
1 <= grid.length <= 500- The grid is square: every row has
grid.lengthentries. - Each entry is either
0or1.