第１１回日本情報オリンピック 予選 E - イルミネーション
お題箱より。
解法
座標の表記について、（縦の座標, 横の座標）という順番で表記することにします。こちらのほうが配列の添字順と合うので都合が良いです。
公式解説と同じく、与えられる領域の外周にもう1つ分の六角形が存在するとして考えると扱いやすいです。入力を1-indexedのまま扱い、 から
までの座標が存在すると思えば良いです。
全ての六角形について「外から建物の中を通らずに到達できる場所」かどうかを判定することを目指します。求めたい答えは、外から到達できる六角形と到達できない六角形が隣接している壁の枚数です。
外周から到達可能な六角形は、例えば以下のような方法で求めることができます。
- 外周にある六角形から、互いに通行可能な六角形を辿っていく幅優先探索を行う。
- 外周にある六角形から、互いに通行可能な六角形を辿っていく深さ優先探索を行う。
- UnionFindを用いて、互いに通行可能な六角形同士を連結し、外周と同じ連結成分に属するか判定する。
どの方法でも構いません。今回は幅優先探索することにしましょう。
ここで少し問題となるのが、ある六角形に隣り合う六角形の座標の求め方です。今回の問題のような座標の付け方では、座標 と隣り合う六角形の座標は縦の座標値
の偶奇に応じて変わります。具体的には以下のようになります（問題文中の図と座標の表記順が逆なので注意）。
が奇数の場合、隣り合う座標は
。
。
これらの隣接する座標のうち通行可能な場所を辿っていくように幅優先探索を行えば良いです。
これで全ての六角形について「外から建物の中を通らずに到達できる場所」かどうかを判定できました。答えを求める際には、外から到達できる六角形全てについて、隣接している外から到達できない六角形の個数を数えて合計すれば良いです。
隣接している六角形の座標を求める処理は、幅優先探索パートと答えを求めるパートの2通りの用途で使います。実装の際には関数化しておくのが良いでしょう。
