#include "mars.h"
#include <string.h>
#include <stdio.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]));
}
int join(int *ds, int i, int j) {
i = find(ds, i);
j = find(ds, j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
string process(vvs ss, int i, int j, int k, int n) {
int n_ = (k + 1) * 2 + 1, m = (n + 1) / 2, l = (m + 1) / 3;
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 {
if (k < l) {
string s(100, '0');
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 < m - 1) {
for (int i1 = 0; i1 < 2; i1++)
for (int j1 = 0; j1 < 2; j1++)
for (int i2 = 0; i2 < 3; i2++)
for (int j2 = 0; j2 < 3; j2++)
if (i == i1 * (n - m) * 2 + i2 * (m - 1 - k) && j == j1 * (n - m) * 2 + j2 * (m - 1 - k))
return ss[i2][j2];
return ss[0][0];
} else if (k == m - 1) {
int i0, j0;
for (i0 = 0; i0 < 2; i0++)
for (j0 = 0; j0 < 2; j0++)
if (i == i0 * (n - m) * 2 && j == j0 * (n - m) * 2)
goto out;
out:
if (i0 == 2)
return ss[0][0];
int m_ = m * 2 + 1, l_ = l * 2 + 1;
string s_(m_ * m_, '0');
for (int i1 = 0; i1 < 3; i1++)
for (int j1 = 0; j1 < 3; j1++)
for (int i2 = 0; i2 < l_; i2++)
for (int j2 = 0; j2 < l_; j2++)
s_[(i1 * (m - l) + i2) * m_ + (j1 * (m - l) + j2)] = ss[i1][j1][i2 * l_ + j2];
string s((n + 1) * (n + 1), '0');
for (i = 0; i <= n; i++)
for (j = 0; j <= n; j++)
s[i * (n + 1) + j] = s_[(i + i0 * n % 2) * m_ + (j + j0 * n % 2)];
int ds[(N + 1) * (N + 1)];
memset(ds, -1, (n + 1) * (n + 1) * sizeof *ds);
for (i = 0; i <= n; i++)
for (j = 0; j <= n; j++)
if (s[i * (n + 1) + j] == '1') {
if (i > 0 && s[(i - 1) * (n + 1) + j] == '1')
join(ds, i * (n + 1) + j, (i - 1) * (n + 1) + j);
if (j > 0 && s[i * (n + 1) + (j - 1)] == '1')
join(ds, i * (n + 1) + j, i * (n + 1) + (j - 1));
}
int rr_[N * 4];
for (i = 0, j = 0; i < n; i++)
rr_[i] = find(ds, i * (n + 1) + j);
for (i = n, j = 0; j < n; j++)
rr_[n + j] = find(ds, i * (n + 1) + j);
for (i = n, j = n; i > 0; i--)
rr_[n * 3 - i] = find(ds, i * (n + 1) + j);
for (i = 0, j = n; j > 0; j--)
rr_[n * 4 - j] = find(ds, i * (n + 1) + j);
int c = 0;
for (i = 0; i < (n + 1) * (n + 1); i++)
if (ds[i] < 0 && s[i] == '1')
c++;
string t(100, '0');
int rr[N_];
if (i0 == 0 && j0 == 0)
for (int h = 0; h <= n * 2; h++)
rr[h] = rr_[(h + n) % (n * 4)];
else if (i0 == 0 && j0 == 1)
for (int h = 0; h <= n * 2; h++)
rr[h] = rr_[(h + 0) % (n * 4)];
else if (i0 == 1 && j0 == 1)
for (int h = 0; h <= n * 2; h++)
rr[h] = rr_[(h + n * 3) % (n * 4)];
else
for (int h = 0; h <= n * 2; h++)
rr[h] = rr_[(h + n * 2) % (n * 4)];
for (int h = 0; h <= n; h++)
if (s[rr[h]] == '0')
c++;
if (i0 == 0 && j0 == 0 && s[rr[n]] == '0')
c--;
char used[(N + 1) * (N + 1)];
for (int h = 0; h < 10; h++)
t[h] = (c >> h & 1) + '0';
memset(used, 0, sizeof used);
for (int h = 0; h <= n * 2; h++)
if (!used[rr[h]])
used[rr[h]] = 1, t[10 + (h << 1 | 0)] = '1';
memset(used, 0, sizeof used);
for (int h = n * 2; h >= 0; h--)
if (!used[rr[h]])
used[rr[h]] = 1, t[10 + (h << 1 | 1)] = '1';
return t;
} 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 ds[N_ * 4], qu[N_];
int c_, cnt;
memset(ds, -1, n_ * 4 * sizeof *ds);
c_ = 0;
for (int i0 = 0; i0 < 2; i0++)
for (int j0 = 0; j0 < 2; j0++) {
string t = ss[i0 * 2][j0 * 2];
int g = 0;
if (i0 == 0 && j0 == 0)
g = 0;
else if (i0 == 0 && j0 == 1)
g = 1;
else if (i0 == 1 && j0 == 1)
g = 2;
else
g = 3;
int c = 0;
for (int h = 0; h < 10; h++)
if (t[h] == '1')
c |= 1 << h;
c_ += c;
cnt = 0;
for (int h = 0; h <= n * 2; h++) {
if (t[10 + (h << 1 | 0)] == '1')
qu[cnt++] = g * n_ + h;
else
join(ds, qu[cnt - 1], g * n_ + h);
if (t[10 + (h << 1 | 1)] == '1')
cnt--;
}
}
for (int g = 0; g < 4; g++)
for (int h = n; h <= n * 2; h++)
if (join(ds, g * n_ + h, (g + 1) % 4 * n_ + n_ - 1 - h))
c_--;
string t(100, '0');
for (int h = 0; h < 10; h++)
t[h] = (c_ >> h & 1) + '0';
return t;
}
}
}
