#include "mars.h"
#include <string.h>
using namespace std;
typedef vector<string> vs;
typedef vector<vs> vvs;
const int N = 20, N_ = N * 2 + 1;
int find(int *ds, int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds, ds[i]));
}
void join(int *ds, int i, int j) {
i = find(ds, i);
j = find(ds, j);
if (i == j)
return;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
}
string process(vvs ss, int i, int j, int k, int n) {
string s(100, '0');
int n_ = (k + 1) * 2 + 1;
if (n == 1) {
int ds[N_ * N_];
memset(ds, -1, n_ * n_ * sizeof *ds);
for (i = 0; i < n_; i++)
for (j = 0; j < n_; j++)
if (ss[i][j][0] == '1') {
if (i > 0 && ss[i - 1][j][0] == '1')
join(ds, i * n_ + j, (i - 1) * n_ + j);
if (j > 0 && ss[i][j - 1][0] == '1')
join(ds, i * n_ + j, i * n_ + (j - 1));
}
int c = 0;
for (i = 0; i < n_ * n_; i++)
if (ds[i] < 0 && ss[i / n_][i % n_][0] == '1')
c++;
string t(100, '0');
for (int h = 0; h < 10; h++)
t[h] = (c >> h & 1) + '0';
return t;
} else {
int m = (n + 1) / 2;
if (k < m) {
for (int i1 = 0; i1 < 3; i1++)
for (int j1 = 0; j1 < 3; j1++)
for (int i2 = 0; i2 < n_ - 2; i2++)
for (int j2 = 0; j2 < n_ - 2; j2++)
s[(i1 + i2) * n_ + (j1 + j2)] = ss[i1][j1][i2 * (n_ - 2) + j2];
return s;
} else if (k < n - 1) {
if (i == (n - 1 - k) * 2 && j == 0)
return ss[2][0];
else if (i == 0 && j == (n - 1 - k) * 2)
return ss[0][2];
if (i == (n - 1 - k) * 2 && j == (n - 1 - k) * 2)
return ss[2][2];
return ss[0][0];
} else {
int m_ = m * 2 + 1;
for (int i1 = 0; i1 < 3; i1 += 2)
for (int j1 = 0; j1 < 3; j1 += 2)
for (int i2 = 0; i2 < m_; i2++)
for (int j2 = 0; j2 < m_; j2++)
s[(i1 * (n - m) + i2) * n_ + (j1 * (n - m) + j2)] = ss[i1][j1][i2 * m_ + j2];
int ds[N_ * N_];
memset(ds, -1, n_ * n_ * sizeof *ds);
for (i = 0; i < n_; i++)
for (j = 0; j < n_; j++)
if (s[i * n_ + j] == '1') {
if (i > 0 && s[(i - 1) * n_ + j] == '1')
join(ds, i * n_ + j, (i - 1) * n_ + j);
if (j > 0 && s[i * n_ + (j - 1)] == '1')
join(ds, i * n_ + j, i * n_ + (j - 1));
}
int c = 0;
for (i = 0; i < n_ * n_; i++)
if (ds[i] < 0 && s[i] == '1')
c++;
string t(100, '0');
for (int h = 0; h < 10; h++)
t[h] = (c >> h & 1) + '0';
return t;
}
}
}
