CCCPaste

USACO 2017 US Open Contest, Bronze - Problem...

#include <bits/stdc++.h>
using namespace std;
ifstream fin("art.in");
ofstream fout("art.out");

const int nmax = 10;
int n;
int c[nmax + 1][nmax + 1];
struct BoundingBox {
int xmin = 1e9, ymin = 1e9;
int xmax = 0, ymax = 0;
} bb[nmax + 1];

void update(BoundingBox& bb, int x, int y) {
bb.xmin = min(bb.xmin, x);
bb.ymin = min(bb.ymin, y);
bb.xmax = max(bb.xmax, x);
bb.ymax = max(bb.ymax, y);
}

bool ok[nmax + 1];

int main() {
fin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
char ch;
fin >> ch;
c[i][j] = ch - '0';
if (c[i][j] == 0) {
continue;
}
ok[c[i][j]] = true;
update(bb[c[i][j]], i, j);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (c[i][j] == 0) {
continue;
}
for (int k = 1; k <= 9; ++k) {
if (k == c[i][j]) {
continue;
}
// vreau sa vad daca (i, j) este inclusa in bounding boxul culorii k
if (bb[k].xmin <= i && i <= bb[k].xmax && bb[k].ymin <= j && j <= bb[k].ymax) {
// culoarea c[i][j] a fost pusa dupa culoarea k
ok[c[i][j]] = false;
}
}
}
}
fout << count(ok + 1, ok + 11, true);
}