<p>You are given a 2D matrix <code>grid</code> consisting of positive integers.</p>

<p>You have to select <em>one or more</em> cells from the matrix such that the following conditions are satisfied:</p>

<ul>
	<li>No two selected cells are in the <strong>same</strong> row of the matrix.</li>
	<li>The values in the set of selected cells are <strong>unique</strong>.</li>
</ul>

<p>Your score will be the <strong>sum</strong> of the values of the selected cells.</p>

<p>Return the <strong>maximum</strong> score you can achieve.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,2,3],[4,3,2],[1,1,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">8</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/07/29/grid1drawio.png" /></p>

<p>We can select the cells with values 1, 3, and 4 that are colored above.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[8,7,6],[8,3,2]]</span></p>

<p><strong>Output:</strong> <span class="example-io">15</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/07/29/grid8_8drawio.png" style="width: 170px; height: 114px;" /></p>

<p>We can select the cells with values 7 and 8 that are colored above.</p>
</div>

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

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 10</code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 100</code></li>
</ul>

             
from scipy.optimize import linear_sum_assignment   
import numpy as np         

# class Solution:
#     INF = 1e6
#     def maxScore(self, grid: List[List[int]]) -> int:
#         sorted_grid = []
#         uniq = set()
#         for row in grid:
#             r = set()
#             for cell in row:
#                 r.add(100-cell)
#                 uniq.add(100-cell)
#             r = sorted(r, reverse=True)
#             sorted_grid.append(r)
#         sorted_grid = sorted(sorted_grid, reverse=True)
#         uniq = list(uniq)
#         uniq = sorted(uniq, reverse=True)
#         m = len(grid)
#         n = len(uniq)
        
#         transformed_grid = [ [self.INF]*n for _ in range(m)]
#         for i in range(m):
#             for j in range(n):
#                 if uniq[j] in sorted_grid[i]:
#                     transformed_grid[i][j] = uniq[j]
#         matrix = []
#         for i in range(m):
#             matrix.append(np.array(transformed_grid[i]))
        
#         matrix = np.array(matrix)   
        
#         row_ind, col_ind = linear_sum_assignment(matrix)
#         su = 0
#         count = 0
#         for i in range(len(row_ind)):
#             if matrix[row_ind[i]][col_ind[i]] == self.INF:
#                 count += 1
#             else:
#                 su += matrix[row_ind[i]][col_ind[i]]
        
#         res = 100*(len(row_ind)-count) - su
#         return int(res)
                
class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        # flatten all the values in the grid and deduplicate
        value_set = set([grid[r][c] for r in range(rows) for c in range(cols)])
        
        # sort values from in descending order
        value_list = sorted(list(value_set))[::-1]

        # create a map mapping from each value to the list of row indexes with these values
        val_to_rows = defaultdict(list)
        for value in value_list:
            val_to_rows[value] = [r for r in range(rows) if value in grid[r]]

        # Run dfs on rows with cell values in descending order.
        def dfs(row_set, remaining_values, score):
            if not remaining_values:
                return score

            value = remaining_values[0]
            remaining_values = remaining_values[1:]

            score_list = []

            for row in val_to_rows[value]:
                if row not in row_set:
                    score_list.append(dfs(row_set | {row}, remaining_values, score + value))
            if not score_list:
                score_list.append(dfs(row_set, remaining_values, score))
            return max(score_list)

        return dfs(set(), value_list, 0)
        
            
               
# # 9 8   6 5
# # 9   7 6
# #   8     5 4 2
# #     7 6 5

# # r =[9]
# # 8 6 5
# # 8 5 4 2
# # 7 6 5

# # r =[9, 8]
# # 6 5
# # 7 6 5

# # r =[9, 8, 7]
# # 6 5

# # r =[9, 8, 7, 6]

70320