<p>You are given four integers, <code>m</code>, <code>n</code>, <code>introvertsCount</code>, and <code>extrovertsCount</code>. You have an <code>m x n</code> grid, and there are two types of people: introverts and extroverts. There are <code>introvertsCount</code> introverts and <code>extrovertsCount</code> extroverts.</p>

<p>You should decide how many people you want to live in the grid and assign each of them one grid cell. Note that you <strong>do not</strong> have to have all the people living in the grid.</p>

<p>The <strong>happiness</strong> of each person is calculated as follows:</p>

<ul>
	<li>Introverts <strong>start</strong> with <code>120</code> happiness and <strong>lose</strong> <code>30</code> happiness for each neighbor (introvert or extrovert).</li>
	<li>Extroverts <strong>start</strong> with <code>40</code> happiness and <strong>gain</strong> <code>20</code> happiness for each neighbor (introvert or extrovert).</li>
</ul>

<p>Neighbors live in the directly adjacent cells north, east, south, and west of a person&#39;s cell.</p>

<p>The <strong>grid happiness</strong> is the <strong>sum</strong> of each person&#39;s happiness. Return<em> the <strong>maximum possible grid happiness</strong>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/05/grid_happiness.png" style="width: 261px; height: 121px;" />
<pre>
<strong>Input:</strong> m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
<strong>Output:</strong> 240
<strong>Explanation:</strong> Assume the grid is 1-indexed with coordinates (row, column).
We can put the introvert in cell (1,1) and put the extroverts in cells (1,3) and (2,3).
- Introvert at (1,1) happiness: 120 (starting happiness) - (0 * 30) (0 neighbors) = 120
- Extrovert at (1,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
- Extrovert at (2,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
The grid happiness is 120 + 60 + 60 = 240.
The above figure shows the grid in this example with each person&#39;s happiness. The introvert stays in the light green cell while the extroverts live on the light purple cells.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
<strong>Output:</strong> 260
<strong>Explanation:</strong> Place the two introverts in (1,1) and (3,1) and the extrovert at (2,1).
- Introvert at (1,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
- Extrovert at (2,1) happiness: 40 (starting happiness) + (2 * 20) (2 neighbors) = 80
- Introvert at (3,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
The grid happiness is 90 + 80 + 90 = 260.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
<strong>Output:</strong> 240
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= m, n &lt;= 5</code></li>
	<li><code>0 &lt;= introvertsCount, extrovertsCount &lt;= min(m * n, 6)</code></li>
</ul>

class Solution:
    def getMaxGridHappiness(self, m: int, n: int, iCount: int, eCount: int) -> int:
        # nums are all really small
        # m*n spots
            # up to 6 people to place
        # 3 options per spot (roughly)
            # so 3**(mn) states??
            # but can only fill 12 spots
            # so kinda like sum(25 choose 1-12)?
                # + 12 work for each to calc score
            # for a given 12 spots, 924 ways to arrange between intro and extra
            # overlaps:
                # only actually diff if n_neighbors is different
                # so, after placing a neighbor, could just check:
                    # no neighbors
                    # 1-4 neighbors
                    # ultimately, have to check each grid placement tho
            # could possibly check:
                # for each of the 12:
                    # not placed
                    # placed w no neighbors
                    # placed w 1-4 neighbors
            # i: never a downside to placing, lowest score is 0
            # e: never a downside to placing, lowest score is 40
            # so we should always place everyone, but just a question of where
            # i: minimize neighbors
            # e: maximize neighbors
                # 4 neighbor e is same as 0 neighbor i
                # 3 neighbor e is better than anything but 0 neighbor i
            # each iter can be placing 1 neighbor
                # look at any unused spot
                # 25**12...

        @lru_cache(None)
        def rec(i, j, icount, ecount, prev_row):
            if icount == 0 and ecount == 0:
                return 0
            if j == n and i == m-1:
                return 0
            if j == n:
                i += 1
                j = 0
#                prev_row = prev_row[-n:]
            # don't place
            best = rec(i,j+1, icount, ecount, (prev_row + (0,))[-n:])
            above = prev_row[0] if i != 0 else 0
            left = prev_row[-1] if j != 0 else 0
            # place i
            if icount > 0:
                score = 120
                # if below an introvert, we both hurt each other
                if above == 1:
                    score -= 60
                elif above == 2:
                    score -= 10
                if left == 1:
                    score -= 60
                elif left == 2:
                    score -= 10
                best = max(best, score+rec(i,j+1,icount-1,ecount,(prev_row + (1,))[-n:]))
            if ecount > 0:
                score = 40
                if above == 1:
                    score -= 10
                elif above == 2:
                    score += 40
                if left == 1:
                    score -= 10
                elif left == 2:
                    score += 40
                best = max(best, score+rec(i,j+1,icount,ecount-1,(prev_row + (2,))[-n:]))
            return best
        return rec(0,0,iCount,eCount, ())


        # 5*5*6*6*x possible states
            # placed: m*n choose 12?
        # duplicate work:
            # pass through a given `placed` m*n times
        # old method:
            # m*n work per iter
            # but, only 12 recursions
            # ~3**12 * 25
        def rec(i, j, icount, ecount, placed):
            if (icount == 0 and ecount == 0) or (i == m-1 and j == n):
                # O(placed^2), could be O(placed)
                d = {(i,j): v for (i,j,v) in placed}
                happiness = 0
                for (i,j), v in d.items():
                    neighbors = len([1 for (i2,j2) in d.keys() if abs(i-i2)+abs(j-j2) == 1])
                    if v == 1:
                        happiness += 120 - 30*neighbors
                    elif v == 2:
                        happiness += 40 + 20*neighbors
                # print('happiness', placed, happiness)
                return happiness
            if j == n:
                i += 1
                j = 0
            # place no one here
            best = rec(i, j+1, icount, ecount, placed)
            if icount > 0:
                # place an introvert
                best = max(best, rec(i, j+1, icount-1,ecount, placed + ((i, j, 1),)))
            if ecount > 0:
                # place an extravert
                best = max(best, rec(i, j+1, icount,ecount-1, placed + ((i, j, 2),)))
            return best
        return rec(0,0,iCount,eCount, ())

45700