知识点:递归,递推
和李煜东的那道例题大体思想上一样,指数枚举第一行的时间复杂度是可以接受的,所以枚举第一行,然后由第一行递推得出后面的行,在中间判断存结果就行,需要注意的是,本题只能0变成1,这个不要想当然我一开始做的时候直接默认01可以互换
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;
const int Inf = 1000000000;
int n, mat[20][20], t[20][20], ans;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
vi chosen;
void calc(int xx) {
if (xx == n + 1) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) t[i][j] = mat[i][j];
}
for (int i = 0; i < sz(chosen); i++) {
if (t[1][chosen[i]]) continue;
t[1][chosen[i]] = 1;
cnt++;
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int temp = t[i - 2][j] + t[i][j] + t[i - 1][j - 1] + t[i - 1][j + 1];
if (temp % 2) {
if (t[i][j]) return;
cnt++; t[i][j] = 1;
}
if (cnt >= ans) return;
}
}
int ok = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int temp = t[i - 1][j] + t[i + 1][j] + t[i][j - 1] + t[i][j + 1];
if (temp % 2) ok = 0;
}
}
if (ok && cnt < ans) ans = cnt;
return;
}
calc(xx + 1);
chosen.pb(xx);
calc(xx + 1);
chosen.pop_back();
}
int main() {
int t;
cin >> t;
for (int k = 1; k <= t; k++) {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) cin >> mat[i][j];
}
ans = Inf;
calc(1);
cout << "Case " << k << ": ";
cout << (ans == Inf ? -1 : ans) << endl;
}
return 0;
}