New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Plantation

Contributed by

imObscure

Medium

0/80

Avg time to solve 20 mins

Success Rate 65 %

0 upvotes

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, Constraints, 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

Auto

Console