# Grid Value

#### You are given a grid of size N*M. There are two types of people, type ‘A’ and type ‘B’ . You are also given the number of people of each type say ‘countA’ is the number of ‘A’ type persons and ‘countB’ is the number of ‘B’ type of persons. The satisfaction of a particular type of person can increase or decrease as follows :

```
The initial satisfaction of a person of type A is 80. It decreases by 20 for each neighbor.
The initial satisfaction of a person of type B is 50. It increases by 10 for each neighbor.
```

#### Your task is to determine the maximum possible grid satisfaction.

##### Note:

```
You may choose exactly how many people you want to be present in the grid.
The total number of people of type ‘A’ living in the grid can be less than ‘countA’ but cannot exceed ‘countA’. Similarly, total number of people of type ‘B’ living in the grid can be less than ‘countB’ but cannot exceed ‘countB’
A person can live in only one cell.
Not more than one person can live in a cell.
Two cells are said to be neighbors if the cells are adjacent and share a boundary.
```

##### Input Format:

```
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.
The first and the only line of each test case contains four space-separated integers ‘N’, ‘M’, ‘countA’, and ‘countB’, denoting the grid’s dimensions and the number of each type of people present.
```

##### Output Format:

```
For each test case, print in a new line an integer denoting the maximum possible grid satisfaction.
```

##### Note:

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= T <= 2
1 <= N,M <= 6
0 <= countA, countB <= min(N*M, 6)
Time Limit: 1sec
```

The approach is to use Recursion along with Bitmasking. We can observe that we only need to know the last M cells we processed. We should only consider the cells at the top and left of the current cell because the right direction will be covered by someone else's left position, and the bottom position will be covered by someone else's top position. If a cell is filled, its contribution is fixed. If a neighbor cell is filled later, then the contribution of the original cell can be calculated towards the neighbor cell only.

**Steps**

- Initialize two variables to maintain bitmasks for each type of person. Let’s call them
**mask_A=0**and**mask_B=0.** - Now, return the value of the recursive function,
**findMaxValue(m,n,countA,countB,mask_A, mask_B).**

**int findMaxValue(m,n,curr_pos,countA_remaining,countB_reamining,mask_A, mask_B)**

- Find the location of the current cell.
**row = curr_pos/n**and**col = curr_pos%n.** - If
**row >= m, return 0.** - Now, define
**n_mask_A = (mask_A << 1) & 63**and**n_mask_B = (mask_B << 1) & 63.** - Now, define
**maxValue = findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining, n_mask_A, n_mask_B). maxValue**is now equal to the value we get if the current cell is left empty. - If
**countA_remaining>0,**- Define
**placingA_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)** - Update
**maxValue = max(maxValue, placingA_cost + findMaxValue(m,n,curr_pos+1,countA_remaining-1, countB_remaining,n_mask_A+1,n_mask_B)**

- Define
- If
**countB_remaining>0,**- Define
**placingB_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)** - Update
**maxValue = max(maxValue, placingB_cost + findMaxValue(m,n,curr_pos+1,countA_remaining, countB_remaining-1,n_mask_A,n_mask_B+1)**

- Define
- Return the value of
**maxValue.**

**int neighborCost( m, n, row, col, mask_A, mask_B, diff)**

- Initialize
**cost = 0** - Define
**top = 1 << (n-1)** - If col > 0 and mask_A & 1, add
**diff-20**to**cost.** - If row > 0 and mask_A & top, add
**diff-20**to**cost.** - If col > 0 and mask_B & 1, add
**diff+10**to**cost.** - If row > 0 and mask_B & top, add
**diff+10**to**cost.** - Return
**cost.**

The approach is to use Dynamic Programming along with Bitmasking. We can observe that we only need to know the last M cells we processed. We should only consider the cells at the top and left of the current cell because the right direction will be covered by someone else's left position, and the bottom position will be covered by someone else's top position. If a cell is filled, its contribution is fixed. If a neighbor cell is filled later, then the contribution of the original cell can be calculated towards the neighbor cell only. We can optimize our solution by storing the values for smaller subproblems in an array so that we don’t require to calculate the answer for the same subproblems again.

**Steps**

- Initialize two variables to maintain bitmasks for each type of person. Let’s call them
**mask_A=0**and**mask_B=0.** - Now, return the value of the recursive function,
**findMaxValue(m,n,,countA,countB,mask_A, mask_B).**

**int findMaxValue(m,n,curr_pos,countA_remaining,countB_reamining,mask_A, mask_B)**

- Find the location of the current cell.
**row = curr_pos/n**and**col = curr_pos%n.** - If
**row >= m, return 0.** - Now, if the value at memo
**[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B]**has been stored already, then return this value after subtracting 1 from it. We are subtracting 1 here because while storing the value, we are adding 1 to it. - Now, define
**n_mask_A = (mask_A << 1) & 63**and**n_mask_B = (mask_B << 1) & 63.** - Now, define
**maxValue = findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining, n_mask_A, n_mask_B). maxValue**is now equal to the value we get if the current cell is left empty. - If
**countA_remaining>0,**- Define
**placingA_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)** - Update
**maxValue = max(maxValue, placingA_cost + findMaxValue(m,n,curr_pos+1,countA_remaining-1, countB_remaining,n_mask_A+1,n_mask_B)**

- Define
- If
**countB_remaining>0,**- Define
**placingB_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)** - Update
**maxValue = max(maxValue, placingB_cost + findMaxValue(m,n,curr_pos+1,countA_remaining, countB_remaining-1,n_mask_A,n_mask_B+1)**

- Define
- Now, make memo
**[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] = maxValue + 1.** - Return the value of
**maxValue.**

**int neighborCost( m, n, row, col, mask_A, mask_B, diff)**

- Initialize
**cost = 0** - Define
**top = 1 << (n-1)** - If col > 0 and mask_A & 1, add
**diff-20**to**cost.** - If row > 0 and mask_A & top, add
**diff-20**to**cost.** - If col > 0 and mask_B & 1, add
**diff+10**to**cost.** - If row > 0 and mask_B & top, add
**diff+10**to**cost.** - Return
**cost.**