Topics

Plantation

Moderate
0/80
Average time to solve is 20m
Contributed by
0 upvote

Problem statement

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.

Example:
``````Input: ‘N’ = 2 ,'GRID' =  [[0,1],[1,1]]

Output: 4
Explanation:
Sam can plant a tree on the only remaining unplanted cell.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1  <= T <= 10
1  <= N <= 500
GRID[i][j] is either 0 or 1.
Time Limit: 1 sec
``````
Sample Input 1 :
``````2
2
0 1
1 1
3
1 0 1
0 0 0
0 0 0
``````
Sample Output 1 :
``````4
3
``````
Explanation Of Sample Input 1 :
``````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.
``````
Sample Input 2 :
``````2
2
0 0
0 0
3
0 1 0
1 0 1
0 1 0
``````
Sample Output 2 :
``````1
5
``````
Console