New update is available. Click here to update.

Topics

Sam is on a plantation drive on his campus. His campus can be represented as an ‘N’x’N’ ‘GRID’ of 0s and 1s. Where cells with 1 represent that there is already a tree and cells with 0 represent that a tree can be planted here.

Sam wants to plant atmost 1 tree in his campus.

Note : It is possible that the grid does not contain any zero.

Return the largest group of trees on the campus after Sam planted 1 tree.

Largest group of trees is the 4-directionally connected group of 1s.

```
Input: ‘N’ = 2 ,'GRID' = [[0,1],[1,1]]
Output: 4
Explanation:
Sam can plant a tree on the only remaining unplanted cell.
```

Detailed explanation

```
1 <= T <= 10
1 <= N <= 500
GRID[i][j] is either 0 or 1.
Time Limit: 1 sec
```

```
2
2
0 1
1 1
3
1 0 1
0 0 0
0 0 0
```

```
4
3
```

```
Test 1:
Sam can plant a tree on the only remaining unplanted cell.
Test 2:
Sam can plant a tree between the two trees, so the largest group would contain 3 trees.
```

```
2
2
0 0
0 0
3
0 1 0
1 0 1
0 1 0
```

```
1
5
```