0

Town Planning

Difficulty: HARD
Avg. time to solve
35 min
Success Rate
50%

Problem Statement

Town planner Ninja is assigned to build new houses in the ninja town for its citizens. The town is in the form of a rectangular grid ‘TOWN[][]’ of (‘M’ * ‘N’) dimensions where 'M' is the number of rows and 'N' is the number of columns. Each cell of the grid can be an 'empty location' (that can be used for house) denoted by '.' or 'Tree' denoted by 'T'.

Ninja wants to meet the demands of the citizens without cutting any of the trees.

Following are the conditions asked by citizens for their house locations :
House should not have a house on its left cell
House should not have a house on its right cell
House should not have a house on its upper-left cell
House should not have a house on its upper-right cell
Town planner Ninja needs your help. Return the maximum number of houses that can be built while meeting the citizens' demands and not cutting any of the trees.

For Example :

Input  :
M = 3 , N = 5
Grid :
. . . T .
. T . . .
T . . T .

In the example above, the maximum number of houses that be built is 8.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then ‘T’ test cases follow:

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

The next ‘M’ lines contain a string of length ‘N’ containing ‘.’ or ‘T’ representing empty space or a Tree, respectively. 
Output Format :
For each test case, print an integer denoting the maximum number of houses that can build following the conditions stated above.

Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 8
1 <= M <= 8
‘TOWN’ = { “.”,"T"}

Where 'TOWN’ denotes the 2-D grid represents whether a cell is empty or not.

Time limit: 1 sec
Sample Input 1 :
1
3 5
. . . T .
. T . . .
T . . T .
Sample Output 1 :
8
Explanation of sample input 1 :
The following diagram represents the above input grid :

The possible optimal arrangement of houses is shown below: 

Hence, a maximum 8 number of houses can be built if demands of citizens are to met and no tree is removed.
Sample Input 2 :
1
3 5
T . . . .
T . T T .
. T . . T
Sample Output 2 :
5
Explanation of sample input 2 :
The following diagram represents the above input grid :

The possible optimal arrangement of houses is shown below:

Hence, a maximum 5 number of houses can be built if the demands of citizens are met and no tree is removed.
Reset Code
Full screen
copy-code
Console