Flipping the matrix


#1

write the program for the below given data

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, and the goal of the game is to maximize the sum of the elements in the n * n submatrix located in the upper-left corner of the 2n * 2n matrix (i.e., its upper-left quadrant).

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. For each matrix, print the maximized sum on a new line.


#2

This a simple problem if you think about it. So a basic explanation is :
Using multiple rotations you can bring any number into the quadrant that you desire. So for any position in the upper left quadrant (position [x][y], where x and y < n) you can move numbers in any quadrant at the following positions to [x][y].
Upper left quadrant [x][2n-1-y] or Upper right quadrant [2n-1-x][y] or lower left quadrant [2n-1-x][2n-1-y] or lower right quadrant because all you need to do then is that for every position (x and y) in the upper left quadrant you need to find the maximum of the numbers at the above positions sum them and print the answer. Program is given below:

int n;
cin >> n;
vector < vector > m(2n, vector(2n));
for (int i=0;i<2n;i++) for (int j=0;j<2n;j++) cin >> m[i][j];
int sum=0;
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
int max=m[i][j];
if (m[i][2n-j-1]>max) max=m[i][2n-j-1];
if (m[2n-i-1][2n-j-1]>max) max=m[2n-i-1][2n-j-1];
if (m[2n-i-1][j]>max) max=m[2n-i-1][j];
sum+=max;
}
}

cout << sum << endl;

Note that time Complexity is O(n) where n is the number of elements in the array.