MMATRIX - SHIFT Operator on Matrix

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>

using namespace std;

const int N = 123;
const int INF = 0x3f3f3f3f;

int a[N][N];
int sum[N], newSum[N];
int n, ans;

void backtrack(int row) {
    if (row > n) {
        ans = *max_element(sum + 1, sum + 1 + n);
        return;
    }
    for (int shift = 0; shift < n; ++shift) {
        for (int i = 1; i <= n; ++i) newSum[i] = sum[i] + a[row][i + shift];
        if (*max_element(newSum + 1, newSum + 1 + n) >= ans) continue;
        for (int i = 1; i <= n; ++i) sum[i] = newSum[i];
        backtrack(row + 1);
        for (int i = 1; i <= n; ++i) sum[i] -= a[row][i + shift];
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while (cin >> n) {
        if (n == -1) break;
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j + n] = a[i][j];
        for (int i = 1; i <= n; ++i) sum[i] = a[1][i];
        ans = INF;
        backtrack(2);
        cout << ans << '\n';
    }
    return 0;
}

Download