algorithmdynamic-programmingbitmask

Placing 1x2 or 2x1 tiles on r x c matrix to achieve maximum sum of covered cells


How can you find the maximum possible sum of values by optimally placing tiles in a matrix rxc where each cell has an integer value?

The goal is to maximize the sum by covering cells with 1x2 or 2x1 tiles.


Solution

  • Consider location (n, k), we have 3 cases:

    1. Place a 1 * 2 tiles
    2. Place a 2 * 1 tiles
    3. Place nothing

    For example:

    Case 1:
    ????
    ????
    ??xx
    
    Case 2:
    ????
    ???x
    ???x
    
    Case 3:
    ????
    ????
    ???.
    

    For case 2, we will record which grid in the next line we have already taken so that we can solve this question by dp.

    We can define:

    sol(x, y, right_incomplete, up_incompletes) 
      is the maximum of point(x, y) in the condition of right_incomplete and up_incomples
    

    So for point (x, y):

    if right_incomplete(which means we a place 1*2 tile in (x, y+1)), we must close this tile at (x, y)

    if up_incomplete(which means we a place 2*1 tile in (x+1, y)), we must close this tile at (x, y)

    if both right_incomplete and up_incomplete, means no feasible solution.

    If it is not right_incomplete and up_incomplete, we have three choices: place 1 * 2, place 2 * 1, or do nothing. With each choice, we will come to a smaller question.

    We take an example:

    enter image description here

    The Red lines mean the up_incompletes which have k grids.

    The Blue line means the right_incomplete.

    The arrows mean there is an incomplete otherwise no.

    Now, we are considering the dark gray grid. Based on our up_incompletes information, we should close this incomplete at this grid, so we have only 1 choice here.

    After we do that, then we come to:

    enter image description here

    We take another example:

    enter image description here

    Since there is no incomplete from this grid, we have three choices, which are:

    Choice 1, do nothing:

    enter image description here

    Choice 2, place a 1 * 2 tile, so there will be a right_incomplete for our next grid:

    enter image description here

    Choice 3, place a 2 * 1 tile, so there will be an up_incomplete for the grid next row with the same column:

    enter image description here

    In summary:

    sol(x, y, right_incomplete, up_incompletes) = 
      max(all_possible_solutions) + take_x_y?array[x][y]:0
    

    And by this way, we can achieve an O(n*k*2^k) solution.

    You can check my code for more details:

    MAX_ANS = 10**100
    
    
    def sol(matrix):
        mem = {}
    
        def _sol(x, y, up_incomplete, right_incomplete):
            p = (x, y, up_incomplete, right_incomplete)
            if up_incomplete[-1] and right_incomplete:
                return -MAX_ANS
            if x == 0 and y == 0:
                if up_incomplete[-1] or right_incomplete:
                    return matrix[x][y]
                else:
                    return 0
            if mem.get(p) is not None:
                return mem[p]
            ans = 0
            if y != 0:
                next_x, next_y = x, y - 1
            else:
                next_x, next_y = x - 1, len(matrix[0]) - 1
    
            if right_incomplete:
                new_up_incomplete = tuple([False]) + up_incomplete[:-1]
                ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, False))
            elif up_incomplete[-1]:
                new_up_incomplete = tuple([False]) + up_incomplete[:-1]
                ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, False))
            else:
                if y != 0:
                    new_up_incomplete = tuple([False]) + up_incomplete[:-1]
                    ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, True))
                if x != 0:
                    new_up_incomplete = tuple([True]) + up_incomplete[:-1]
                    ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, False))
    
                new_up_incomplete = tuple([False]) + up_incomplete[:-1]
                ans = max(ans, _sol(next_x, next_y, new_up_incomplete, False))
    
            mem[p] = ans
            return ans
    
        return _sol(len(matrix) - 1, len(matrix[0]) - 1, tuple([False]*len(matrix[0])), False)
    
    
    test_1 = [
        [1, 2, 3]
        , [4, -5, -6]
    ]
    
    test_2 = [
         [2, 6, 3, 1]
        , [6, 5, 6, 1]
        , [2, -6, 2, 1]
    ]
    
    test_3 = [
         [10, -5]
        , [-5, 2]
    ]
    
    print(sol(test_1))
    print(sol(test_2))
    print(sol(test_3))