Flipping the Matrix [Hacker Rank]

Question

Sean invented a game involving a 2n * 2n matrix where each cell of the matrix contains an integer. He can reverse any of its rows or columns any number of times. The goal of the game is to maximize the sum of the elements in the n * n submatrix located in the upper-left quadrant of the matrix.

Given the initial configurations for q matrices, help Sean reverse the rows and columns of each matrix in the best possible way so that the sum of the elements in the matrix's upper-left quadrant is maximal.

Example

1 2
3 4

It is 2 2 and we want to maximize the top left quadrant, a 1 1 matrix. Reverse row 1:

1 2
4 3

And now reverse column 0:

4 2
1 3

The maximal sum is 4.

Function Description

Complete the flippingMatrix function in the editor below.

flippingMatrix has the following parameters:

• int matrix[2n][2n]: a 2-dimensional array of integers

Returns

• int: the maximum sum possible.

Input Format

The first line contains an integer q , the number of queries.

The next q sets of lines are in the following format:

The first line of each query contains an integer, n.
Each of the next 2n lines contains 2n space-separated integers matrix[i][j] in row of the matrix.

Constraints

• 1 <= q <= 16
• 1 <= n <= 128
• 0 <= matrix[i][j] <= 4096, where 0 <= i,j < 2n

Sample Input

STDIN
1
2
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108

Sample Output

414

풀이

def flippingMatrix(matrix):
    sum = 0
    lm = len(matrix)
    quad = lm//2
    for i in range(quad):
        for j in range(quad):
            p1 = matrix[i][j]
            p2 = matrix[i][lm-j-1]
            p3 = matrix[lm-i-1][j]
            p4 = matrix[lm-i-1][lm-j-1]
            sum += max(p1, p2, p3, p4)
    return sum
   

알고리즘은 함께 공부하는 근영오빠의 도움을 받았다.
이미지에서 같은색으로 표시한 것들끼리는 자유롭게 움직일 수 있다. 모든 색은 각 4개씩 있다. 이 4개 중 가장 큰 값을 모두 더하면 답이된다.

결국 이 matrix에서 각 네 모서리의 좌표를 어떻게 표시할지 고민하는 문제다.