Problem D. Hall of Mirrors 問題紹介
鏡の部屋にいて、反射して映った自分をどれだけ見つけられるか…という問題です。
今回の Qualification Round の中で一番難しい問題でした。（解けませんでしたorz）
部屋は正方形のグリッド(マス)で構成されています。
各マスは四方が鏡になっているか、何もないか、中央に自分がいます。
計算上自分はとても小さくて、反射の邪魔になったり体の一部だけが反射したりしないことになっています。（数学的なお約束ですね）
部屋はもやもやしていて、D マス以内しか視界がありません。
例：
###### # 四方が鏡の壁
#..X.# . 何もない空間
#.#..# X 自分がいる場所
#...##
###### D=3
このとき、図の真上の方向を見ると、鏡に映った自分を見ることができます。壁（鏡）まで0.5マス、反射して自分がいるところまで0.5マスで合計1マスの距離なので、視界（D=3）の範囲内です。
同様に図の右（真横）の方向を見た場合も、壁まで1.5マス、反射して1.5マスの計3マスの距離で自分の反射を見ることができます。
下方向や左方向は反射した自分までの距離が5マスとなるので見ることができません。
光は直進し、鏡に当たると入射角と同じ角度で反射します。ごく普通の鏡と同じ光の反射をします。
壁（鏡）の角をかすめる場合、自分はとても小さいので、スルッとすり抜けることができます。
角にぶつかるとそこで光が止まってしまいます。
元々自分がいた場所（のマスの中央）に光が戻ってきたら「反射した自分を見る」ことができます。
ぐるっと見回して反射した自分をいくつ見つけられるか求める問題です。
入力データ:
最初の行は問題数 T。以降 T問のデータが続きます。
問題データの1行目はスペースで区切られた3つの整数で、部屋の幅 W、部屋の高さ H、視界 D。次に H行の部屋データが続きます。
部屋データは次の通りです。
'#' 四方が鏡の壁
'.' 何もない空間
'X' 自分がいる場所
データ制限:
- 3 ≤ H, W ≤ 30
- 1 ≤ D ≤ 50
- 部屋データには 'X' が必ず1つ含まれる
- 部屋データの1行目、最後の行、各行の最初と最後は '#' となる（部屋は鏡で囲まれている）
- Small input の場合: 部屋の内側には壁（鏡）がない（部屋の周囲を囲む壁のみ）
0 件のコメント:
コメントを投稿