0

Maximum Students

Difficulty: EASY
Contributed By
Ankush Gupta
Avg. time to solve
50 min
Success Rate
60%

Problem Statement

The Ultimate Ninja Ankush, has prepared a test for all of his fellow Ninja students, but since he is the Ultimate Ninja, he does not like cheating, and since his students are also ninjas, they broke some chairs in the dojo while practicing their moves.

The class consists of ‘M’ * ‘N’ seats, represented in a matrix ‘SEATS’. Among the seats, some of the seats are broken. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character, denoting that the seat can be occupied. A Ninja can’t sit in a broken seat.

Ankush wants to avoid cheating at any cost. According to his observations, a student can see the answers of four neighboring students sitting next to the left, right, upper left, and upper right, but they cannot see the answers of the student sitting directly in front or behind him. Ankush is very busy so he wants to use the dojo to the fullest. More formally he wants to know the maximum number of ninja students that can be placed in the dojo.

For example

Given:
‘M’ = 3, ‘N’ = 3.
‘SEATS’ = {
   {‘.’, ‘.’, ‘.’},
   {‘#’,’#’, ‘#’},
   {‘.’,’.’,’.’} 
   }
The answer will be 4, since 4 students can be placed at the four corners, i.e. (0,0), (2,2), (2,0), and (0,2) such that no cheating is possible.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘M,’ where ‘M’ is the number of rows in ‘SEATS’ and ‘N’ where ‘N’ is the number of columns in ‘SEATS’.

The next ‘M’ line contains ‘N’ space-separated integers which tell if the seat is broken or in good condition.
Output Format :
For each test case, You are supposed to return an integer that denotes the maximum number of students that can be placed such that no cheating is possible.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10
1 <= ‘M’ <= 10

Time Limit: 1sec.

Sample Input 1 :

2
3 3
. . .
# # #
. . .
2 4
# . # . 
# # . .

Sample Output 1 :

4
3  

Explanation of the Sample Input 1:

In the first test case, The answer will be 4, since 4 students can be placed at the four corners, i.e. (0,0), (2,2), (2,0), and (0,2) such that no cheating is possible.


In the second test case, The answer will be 3, since we can place 3 students at 3 different places, i.e. (0,1), (0,3), (1,3), such that no cheating is possible. 

Sample Input 2 :

2
3 3
. . . 
# . # 
# . . 
2 4
. # # # 
# . . . 

Sample Output 2 :

3
2
Reset Code
Full screen
copy-code
Console