問題一覧 > 通常問題

No.3676 Cuboid Alignment

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : 👑 みうね / テスター : harurun TKTYI
お気に入りにしたユーザー ProblemId : 13846 / 自分の提出
問題文最終更新日: 2026-08-27 11:19:34
yukicoder contest 512 BONSAI (順位表) の他の問題:

問題文

同じ大きさの $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もしくは右上の雲マークをクリックしてアカウントを作成してください。