MMATRIX.cpp

#include <iostream>
using namespace std;

const int MAX_N = 7;
const int MAX_INT = (2 << 30) - 1;
const int MIN_INT = -(2 << 30);

int N = 0, result;
int A[MAX_N][MAX_N];
int temp[MAX_N];

/**
* Tìm ra giá trị lớn nhất của mỗi cột
*/
int maxOfColumnSum() {
	int M = MIN_INT;
	
	for (int c = 0; c < N; c++) {
		int colSum = 0;

		for (int r = 0; r < N; r++) {
			colSum += A[r][c];
		}

		if (colSum > M) M = colSum;
	}

	return M;
}

void shift(int r, int step) {
	// copy sang mảng trung gian
	for (int j = 0; j < N; j++) {
		temp[(j + step) % N] = A[r][j];
	}

	// copy ngược lại mảng A giá trị của hàng r sau khi dịch chuyển
	for (int j = 0; j < N; j++) {
		A[r][j] = temp[j];
	}
}

void unshift(int r, int step) {
	// Dịch ngược step đơn vị giống với dịch xuôi (N - step) đơn vị
	shift(r, N - step);
}

void scan(int r) {
	// Điều kiện dừng
	if (r == N - 1) {
		int M = maxOfColumnSum();
		if (M < result) result = M;
		return;
	}

	for (int step = 0; step < N; step++) {
		// Dịch hàng r với bước nhảy step
		shift(r, step);

		scan(r + 1);
		
		// Trả lại trạng thái của hàng r 
		// bằng cách dịch ngược lại với bước nhảy step
		unshift(r, step);
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	while (true) {
		// Nhập giá trị của N và ma trận A
		cin >> N;
		if (N == -1) break;
		
		// Khởi tạo giá trị của result ứng với mỗi test case
		result = MAX_INT;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> A[i][j];
			}
		}

		// Bắt đầu duyệt đệ quy từ hàng 0 đến hết 
		scan(0);

		cout << result << endl;
	}

	return 0;
}