COVID 19

0

0 votes
implementation, Matrix
Problem

Three friends Aditya ,Saransh and Aviral are spreading awareness regarding COVID 19. They have come across " + " sign that is use by  hospitals, nursing homes, clinics, dispensary, ambulances, etc.

This sign is used by Doctors  so that they can be easily identified, especially during an emergency.

They are Given a  N X N binary matrix and their task is to find size of the largest ‘+’ formed by all 1s. Help them to complete the task.

Input:
First line contains an integer TT test cases follow.
First line of each case contains  integer N that is order of square matrix (N*N).
Then it contains N*N elements (all the elements of the matrix)

Output:
For each test case, output is the integer M (it is the total number of 1's present in the "+" sign);

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10000

Sample Input:                                                                       Sample Output:

2

5                                                                                                       5

1 0 1 0 1
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
1 0 0 0 1

7                                                                                                      9

0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0

                                                                                                        

Explanation:

In first test case where input is 5 (value of N),we can observe a "+" sign formed in which total 1's is 5;

In Second  test case where input is 7 (value of N),,we can observe a "+" sign formed in which total 1's is 9;

Note: Copy and paste is disabled for all the questions. Try not to use other ides.

Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?