Maximize Grid Happiness
You are given four integers, m, n, introvertsCount, and extrovertsCount. You have an m x n grid, and there are two types of people: introverts and extroverts. There are introvertsCount introverts and extrovertsCount extroverts.
You should decide how many people you want to live in the grid and assign each of them one grid cell. Note that you do not have to have all the people living in the grid.
The happiness of each person is calculated as follows:
- Introverts start with
120happiness and lose30happiness for each neighbor, whether introvert or extrovert. - Extroverts start with
40happiness and gain20happiness for each neighbor, whether introvert or extrovert.
Neighbors live in the directly adjacent cells north, east, south, and west of a person's cell.
The grid happiness is the sum of each person's happiness. Return the maximum possible grid happiness.
Example 1
Input
m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2Output
240Putting the introvert at (1,1) and the extroverts at (1,3) and (2,3) gives happiness 120 + 60 + 60 = 240.
Example 2
Input
m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1Output
260Placing introverts at (1,1) and (3,1) and the extrovert at (2,1) gives happiness 90 + 80 + 90 = 260.
Constraints
- 1 <= m, n <= 5
- 0 <= introvertsCount, extrovertsCount <= min(m * n, 6)