1053. Making a Large Island

Given an n x n binary grid, you may change at most one 0 to 1. Return the size of the largest island (land connected 4-directionally) achievable after at most one such change. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the largest achievable island.

Examples

Input: {"grid":[[1,0],[0,1]]}
Output: 3
Explanation: Flipping one 0 joins two islands.

Input: {"grid":[[1,1],[1,0]]}
Output: 4
Explanation: Flip the last 0.

Input: {"grid":[[1,1],[1,1]]}
Output: 4
Explanation: Already all land.

Constraints

• 1<=n<=500

Asked by