Flipping the Matrix

Problem: Flipping the Matrix

In this problem, each single location in the upper-left quarter can be replaced by other 3 numbers: the number reachable by horizontal flipping, the number reachable by vertical flipping and the number reachable by operating each flipping once.

For example, in the following matrix

$matrix = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix}$

If we want 6 changed to 7 and remain other numbers in the upper-left quarter the same, we can first do a horizontal flip.

$matrix = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 8 & 7 & 6 & 5 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix}$

Then we need to make number 5 come back. We can do vertical flip in 1st and 4th column.

$matrix = \begin{bmatrix} 13 & 2 & 3 & 16 \\ 9 & 7 & 6 & 12 \\ 8 & 10 & 11 & 5 \\ 1 & 14 & 15 & 4 \end{bmatrix}$

Then we can do a horizontal flip in the 3rd row.

$matrix = \begin{bmatrix} 13 & 2 & 3 & 16 \\ 9 & 7 & 6 & 12 \\ 5 & 11 & 10 & 8 \\ 1 & 14 & 15 & 4 \end{bmatrix}$

At last we do a vertical flip on 1st column and we can get number 5 back.

$matrix = \begin{bmatrix} 1 & 2 & 3 & 16 \\ 5 & 7 & 6 & 12 \\ 9 & 11 & 10 & 8 \\ 13 & 14 & 15 & 4 \end{bmatrix}$

This process proves that we can achieve a upper-left quarter with biggest sum by assigning biggest possible number from 4 choices to each location.

Code in Python:

q = input()
for _ in xrange(q): 
    n = input() 
    m = [] 
    for i in xrange(2*n): 
        m.append(map(int, raw_input().strip().split(' '))) 
    res = 0 
    for i in xrange(n): 
        for j in xrange(n): 
            res += max([m[i][j], m[2*n-i-1][j], m[i][2*n-j-1], m[2*n-i-1][2*n-j-1]])
    print res