Problem Statement
There is a shortcake in the shape of a $2H \times 2W$ grid. The cell at the $i$-th row from the top and the $j$-th column from the left is denoted as cell $\def\mydef{\def}\mydef\s#1{\left(#1\right)}\mydef\m#1{\left[#1\right]}\mydef\b#1{\left\{#1\right\}}\mydef\abs#1{\left\lvert#1\right\rvert}\s{i, j}$ . Cell $\s{i, j}$ has one strawberry on it if $S_{i, j} =$ o, and nothing if $S_{i, j} =$ x. It is guaranteed that exactly $2HW$ cells have strawberries.
Divide each cell of this shortcake into regions A and B so that all of the following conditions are satisfied:
- Every cell belongs to exactly one of regions A and B.
- Both regions A and B are connected. That is, for any two cells in the same region, one can move between them by repeatedly moving to an adjacent cell (sharing an edge) in the same region.
- Both regions A and B contain exactly $2HW$ cells each.
- Both regions A and B contain exactly $HW$ strawberries each.
It can be proved that such a partition always exists.
You are given $T$ test cases; solve each of them.
$\sum HW \leq 10^6$.
Tutorial
Find a Hamiltonian cycle first. Hence, each segment of the cycle is a connected component.
Then, we can find a segment with exactly $HW$ strawberries, so that the other connected component also has exactly $HW$ strawberries. In this way, when we shift the segment by one cell, the change in the number of strawberries in the segment will be at most 1, which means that we can always find such a segment.
Prefix sums may be a good way to implement it.
Code
public static int rbtree(int TEST_NUMBER, String[] args) {
int h = bin.Int() * 2;
int w = bin.Int() * 2;
char[][] a = new char[h][w];
for (int i = 0; i < h; i++) {
String s = bin.next();
for (int j = 0; j < w; j++) a[i][j] = s.charAt(j);
}
Pair<Integer, Integer>[] ord = new Pair[h * w];
int cnt = 0;
for (int i = w - 1; i >= 0; i--) ord[cnt++] = new Pair<>(0, i);
for (int i = 0; i < w; i++) {
if (i % 2 == 0) {
for (int j = 1; j < h; j++) ord[cnt++] = new Pair<>(j, i);
} else {
for (int j = h - 1; j >= 1; j--) ord[cnt++] = new Pair<>(j, i);
}
}
cnt = 0;
int[] ps = new int[h * w];
ps[0] = a[ord[0].x][ord[0].y] == 'x' ? 1 : 0;
for (int i = 1; i < h * w; i++) {
if (a[ord[i].x][ord[i].y] == 'x') ps[i] = ps[i - 1] + 1;
else ps[i] = ps[i - 1];
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) a[i][j] = 'A';
}
for (int i = 0; i < h * w / 2; i++) {
if (ps[i + h * w / 2 - 1] - (i == 0 ? 0 : ps[i - 1]) == h * w / 4) {
for (int j = i; j < i + h * w / 2; j++) a[ord[j].x][ord[j].y] = 'B';
for (int _i = 0; _i < h; _i++) {
for (int _j = 0; _j < w; _j++) cout.print(a[_i][_j]);
cout.println();
}
return 0;
}
}
return 0;
}