No.3676 Cuboid Alignment
問題文
同じ大きさの $2$ つの直方体 $A, B$ があります。 各直方体は、左右方向に $X$ 個、前後方向に $Y$ 個、上下方向に $Z$ 個の小立方体を格子状に並べたものであり、合計 $XYZ$ 個の小立方体からなります。 直方体 $A$ において、左から $x$ 番目、手前から $y$ 番目、下から $z$ 番目($1\le x\le X$, $1\le y\le Y$, $1\le z\le Z$)の位置を $(x,y,z)$ とします。この位置にある小立方体を $A_{x,y,z}$ と表します。 同様に、直方体 $B$ の位置 $(x,y,z)$ にある小立方体を $B_{x,y,z}$ と表します。 各小立方体の種類は、黒色の不透明ブロック、白色の不透明ブロック、透明ブロックのいずれかです。
直方体 $B$ に対して、以下の操作を好きな順序で $0$ 回以上行うことができます。
- 操作 $1$:一番左の層を取り除き、一番右に置く。
- 操作 $2$:一番手前の層を取り除き、一番奥に置く。
- 操作 $3$:一番下の層を取り除き、一番上に置く。
厳密には、各操作によって直方体 $B$ のすべての小立方体が同時に次のように移動します。
- 操作 $1$:操作前に位置 $(x,y,z)$ にあった小立方体は、$x=1$ ならば位置 $(X,y,z)$ へ、$2\le x\le X$ ならば位置 $(x-1,y,z)$ へ移動する。
- 操作 $2$:操作前に位置 $(x,y,z)$ にあった小立方体は、$y=1$ ならば位置 $(x,Y,z)$ へ、$2\le y\le Y$ ならば位置 $(x,y-1,z)$ へ移動する。
- 操作 $3$:操作前に位置 $(x,y,z)$ にあった小立方体は、$z=1$ ならば位置 $(x,y,Z)$ へ、$2\le z\le Z$ ならば位置 $(x,y,z-1)$ へ移動する。
操作後も、位置 $(x,y,z)$ にある小立方体を $B_{x,y,z}$ と表します。いずれの操作でも、各小立方体の色は変化しません。
操作を終えた後、$2$ つの直方体の同じ位置にある小立方体同士を比較します。 このとき、$A_{x,y,z}$ と $B_{x,y,z}$ がともに不透明ブロックであり、かつ一方が黒色、もう一方が白色であるような位置 $(x,y,z)$ の個数を不整合数と定義します。
不整合数の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられます。
$X\ Y\ Z$ $A_1$ $A_2$ $\vdots$ $A_Z$ $B_1$ $B_2$ $\vdots$ $B_Z$
ここで、$A_z \ (1\le z\le Z)$ は、直方体 $A$ における下から $z$ 番目の層を表すデータであり、以下の $Y$ 行で与えられます。
$A_{z,1}$
$A_{z,2}$
$\vdots$
$A_{z,Y}$
各文字列 $A_{z,y} \ (1\le y\le Y)$ は長さ $X$ であり、その $x$ 文字目 $(1\le x\le X)$ は小立方体 $A_{x,y,z}$ を表します。
$B_z$ についても同様に、$B_{z,y}$ の $x$ 文字目が小立方体 $B_{x,y,z}$ を表します。
各文字は、小立方体の種類を次のように表します。
B:黒色の不透明ブロックW:白色の不透明ブロック.:透明ブロック
各直方体について、下の層から上の層へ、各層では手前の行から奥の行へという順に、$Z \times Y$ 行の文字列が与えられます。 直方体 $A$ を表す $Z \times Y$ 行の後に、直方体 $B$ を表す $Z \times Y$ 行が続きます。これらの間に空行は含まれません。
制約
- $2\le X, Y, Z$
- $XYZ\le 2^{18}$
- 入力される文字列は
B,W,.のみからなる - 入力される数値はすべて整数
出力
不整合数の最小値を出力し、最後に改行してください。
サンプル
サンプル1
入力
3 2 2 BWB BWB B.W BW. .BB WWW WBW BBW
出力
2
操作を行わない場合の不整合数は $5$ です。 直方体 $B$ に対して、操作 $1$ を $1$ 回行った後、操作 $3$ を $1$ 回行うと、不整合数は $2$ になります。 どのように操作しても不整合数を $1$ 以下にはできないため、答えは $2$ です。
サンプル2
入力
2 2 2 BB BB WW WW WW WW BB BW
出力
1
操作を行わない場合の不整合数は $7$ です。直方体 $B$ に対して操作 $3$ を $1$ 回行うと、不整合数は $1$ になり、これが最小です。
サンプル3
入力
2 2 2 B. .. .. .. .W .. .. ..
出力
0
操作を行わない場合、$A_{1,1,1}$ は黒色の不透明ブロックであり、$B_{2,1,1}$ は白色の不透明ブロックです。一方、$B_{1,1,1}$ と $A_{2,1,1}$ は透明ブロックです。このように、少なくとも一方が透明ブロックである位置は、不整合数には数えません。
サンプル4
入力
2 2 2 WB BB BB BB BB BW BB BB
出力
0
直方体 $B$ に対して、操作 $1$ を $1$ 回行った後、操作 $2$ を $1$ 回行うと、すべての位置で色が一致します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
harurun