No.3676 Cuboid Alignment
Problem Statement
There are $2$ cuboids $A, B$ of the same size. Each cuboid consists of small cubes arranged in a grid, with $X$ cubes in the left-right direction, $Y$ cubes in the front-back direction, and $Z$ cubes in the up-down direction, for a total of $XYZ$ small cubes. In cuboid $A$, the position that is $x$-th from the left, $y$-th from the front, and $z$-th from the bottom ($1\le x\le X$, $1\le y\le Y$, $1\le z\le Z$) is denoted by $(x,y,z)$. The small cube at this position is denoted by $A_{x,y,z}$. Similarly, the small cube at position $(x,y,z)$ of cuboid $B$ is denoted by $B_{x,y,z}$. The type of each small cube is one of the following: a black opaque block, a white opaque block, or a transparent block.
You may perform the following operations on cuboid $B$, in any order, $0$ or more times.
- Operation $1$: Remove the leftmost layer and place it at the far right.
- Operation $2$: Remove the frontmost layer and place it at the very back.
- Operation $3$: Remove the bottom layer and place it on the top.
Formally, each operation moves all the small cubes of cuboid $B$ simultaneously as follows.
- Operation $1$: A small cube that was at position $(x,y,z)$ before the operation moves to position $(X,y,z)$ if $x=1$, and to position $(x-1,y,z)$ if $2\le x\le X$.
- Operation $2$: A small cube that was at position $(x,y,z)$ before the operation moves to position $(x,Y,z)$ if $y=1$, and to position $(x,y-1,z)$ if $2\le y\le Y$.
- Operation $3$: A small cube that was at position $(x,y,z)$ before the operation moves to position $(x,y,Z)$ if $z=1$, and to position $(x,y,z-1)$ if $2\le z\le Z$.
Even after the operations, the small cube at position $(x,y,z)$ is denoted by $B_{x,y,z}$. No operation changes the color of any small cube.
After finishing the operations, compare the small cubes at the same positions of the $2$ cuboids. The mismatch count is defined as the number of positions $(x,y,z)$ such that $A_{x,y,z}$ and $B_{x,y,z}$ are both opaque blocks, with one being black and the other being white.
Find the minimum possible mismatch count.
Input
The input is given from standard input in the following format.
$X\ Y\ Z$ $A_1$ $A_2$ $\vdots$ $A_Z$ $B_1$ $B_2$ $\vdots$ $B_Z$
Here, $A_z \ (1\le z\le Z)$ is the data representing the $z$-th layer from the bottom of cuboid $A$, given in the following $Y$ lines.
$A_{z,1}$
$A_{z,2}$
$\vdots$
$A_{z,Y}$
Each string $A_{z,y} \ (1\le y\le Y)$ has length $X$, and its $x$-th character $(1\le x\le X)$ represents the small cube $A_{x,y,z}$.
Likewise for $B_z$, the $x$-th character of $B_{z,y}$ represents the small cube $B_{x,y,z}$.
Each character represents the type of a small cube as follows.
B: a black opaque blockW: a white opaque block.: a transparent block
For each cuboid, $Z \times Y$ lines of strings are given, in order from the bottom layer to the top layer, and within each layer from the front row to the back row. The $Z \times Y$ lines representing cuboid $A$ are followed by the $Z \times Y$ lines representing cuboid $B$. There are no blank lines between them.
Constraints
- $2\le X, Y, Z$
- $XYZ\le 2^{18}$
- The input strings consist only of
B,W,. - All numbers in the input are integers
Output
Output the minimum mismatch count, followed by a newline.
Sample
Sample 1
Input
3 2 2 BWB BWB B.W BW. .BB WWW WBW BBW
Output
2
If no operations are performed, the mismatch count is $5$. If you perform operation $1$ on cuboid $B$ $1$ time and then operation $3$ $1$ time, the mismatch count becomes $2$. No sequence of operations can make the mismatch count $1$ or less, so the answer is $2$.
Sample 2
Input
2 2 2 BB BB WW WW WW WW BB BW
Output
1
If no operations are performed, the mismatch count is $7$. If you perform operation $3$ on cuboid $B$ $1$ time, the mismatch count becomes $1$, which is the minimum.
Sample 3
Input
2 2 2 B. .. .. .. .W .. .. ..
Output
0
If no operations are performed, $A_{1,1,1}$ is a black opaque block and $B_{2,1,1}$ is a white opaque block. On the other hand, $B_{1,1,1}$ and $A_{2,1,1}$ are transparent blocks. Positions like these, where at least one of the blocks is transparent, are not counted in the mismatch count.
Sample 4
Input
2 2 2 WB BB BB BB BB BW BB BB
Output
0
If you perform operation $1$ on cuboid $B$ $1$ time and then operation $2$ $1$ time, the colors match at all positions.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
harurun