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 )

Input Format :

The first line of the input contains an integer, ‘T’, denoting the number of test cases.

The first line of each test case contains an integer, 'N’, denoting the size of the (NxN)campus.

The next ‘N’ lines of each test case contain N integers (0 or 1), denoting unplanted and plated area.

Output format :

Return an integer, denoting the largest group of trees on the campus after Sam planted a tree.

Constraints :

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

Sample Input 1 :

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 :

Sample Output 2 :

1
5

Console