#include "mars.h"
#include <algorithm>
#define pb push_back
using namespace std;
const int LEN = 100;
const int d_i[4] = {1, 0, -1, 0};
const int d_j[4] = {0, 1, 0, -1};
int N;
vector<vector<bool>> grid;
vector<vector<bool>> visited;
void decode(string& h) {
grid.resize(N, vector<bool>(N));
visited.assign(N, vector<bool>(N, false));
int t = 0;
for (int k = 0; k < N; k++) {
int j = N - 1 - k;
for (int i = N - 1; i >= j; i--) {
grid[i][j] = h[t] - '0';
t++;
}
int i = N - 1 - k;
for (int j = i + 1; j < N; j++) {
grid[i][j] = h[t] - '0';
t++;
}
}
}
void floodfill(int i, int j) {
if (visited[i][j] || !grid[i][j]) {
return;
}
visited[i][j] = true;
for (int d = 0; d < 4; d++) {
int n_i = i + d_i[d];
int n_j = j + d_j[d];
if (0 <= min(n_i, n_j) && max(n_i, n_j) < N) {
floodfill(n_i, n_j);
}
}
}
string process(vector<vector<string>> a, int i, int j, int k, int n)
{
int side = 2 * n + 1;
if (side * side > LEN) {
return {};
}
if (max(i, j) != 2 * (n - k - 1)) {
return a[0][0];
}
char state = a[0][0][0];
if (i > j) {
int prv = 2 * n - (i + 2) + 1;
a[0][0] = a[2][0];
a[0][0][prv] = a[1][0][0];
a[0][0][prv + 1] = state;
}
else if (j > i) {
int prv = 2 * n - (j + 2) + 1;
a[0][0] = a[0][2];
a[0][0][prv] = a[0][1][0];
a[0][0][prv + 1] = state;
}
else {
int len = (2 * n - (i + 2) + 1);
int pos = len * len;
a[0][0] = a[2][2];
for (int i = 0; i < len; i++) {
a[0][0][pos] = a[2][1][i];
pos++;
}
a[0][0][pos] = a[1][1][0];
pos++;
for (int i = 0; i < len; i++) {
a[0][0][pos] = a[1][2][len - 1 - i];
pos++;
}
for (int i = 0; i < len; i++) {
a[0][0][pos] = a[2][0][i];
pos++;
}
a[0][0][pos] = a[1][0][0];
a[0][0][pos + 1] = state;
a[0][0][pos + 2] = a[0][1][0];
pos = pos + 3;
for (int i = 0; i < len; i++) {
a[0][0][pos] = a[0][2][len - 1 -i];
pos++;
}
}
if (i != 0 || j != 0) {
return a[0][0];
}
N = 2 * n + 1;
if (n > 2) {
return {};
}
decode(a[0][0]);
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j] == false && grid[i][j]) {
cnt++;
floodfill(i, j);
}
}
}
a[0][0].clear();
while (cnt) {
a[0][0].pb((cnt % 2) + '0');
cnt /= 2;
}
a[0][0].resize(100, '0');
return a[0][0];
}
