Submission #2151866

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
const int INF = 1e9;

int n;
string a[N];
int res = INF;

int cnt_row(int row) {
    int ret = 0;
    for (int col = 0; col < n; ++col) {
        ret += a[row][col] == '#';
    }
    return ret;
}

int cnt_col(int col) {
    int ret = 0;
    for (int row = 0; row < n; ++row) {
        ret += a[row][col] == '#';
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int bad = 0;
    for (int col = 0; col < n; ++col) {
        bad += (cnt_col(col) != n);
    }
    for (int row = 0; row < n; ++row) {
        int cur = cnt_row(row);
        if (cur == n) {
            // contains all black cells
            res = min(res, bad);
        } else {
            // has to be changed
            bool found = false;
            for (int i = 0; i < n; ++i) if (a[i][row] == '#') found = true;
            if (found) res = min(res, n - cur + bad);
        }
    }

    if (res != INF) printf("%d\n", res); else printf("-1\n");
}

Submission Info

Judge Result