たくあんポリポリ

勉強したことを載せていきます。( 主に、C#/ Algorithm / AtCoder / Unity / 最近はKaggleとPython )

【AtCoder】【C#】AtCoder Beginner Contest 151 D問題 - Maze Master

f:id:c_taquna:20200115005201p:plain

はじめに

本記事のテーマ

AtCoder Beginner Contest 151 D問題 - Maze Master の解き方について説明します。

問題へのリンク

atcoder.jp

問題の概要

  • 縦 H マス、横 W マスの H×Wマスからなる迷路が与えられる
  • 任意のスタートとゴールを設定し、移動回数が最小になるようにしてスタートからゴールまで移動する
  • スタートとゴールの位置を適切に定めたとき、青木君の移動回数は最大で何回になるか求める

本題

問題の考察

問題を読み解いてみます。スタートを設定したら移動回数が最小になるようにゴールに移動する→つまり、スタートからゴールまで最短経路を通るということと考えられます。

スタートとゴールを任意に設定した時に移動回数は最大で何回になるか→つまり、スタートとゴールのすべての組み合わせについて、最も離れるように設定する

これをまとめると、

  • 最も離れているスタートとゴールを設定し、スタートからゴールまで最短経路を通る時の移動回数を求めよ

と言い換えられます。

問題の解き方

与えられた迷路の通過可能なすべてのマスを対象に、各マスから最も遠い到達可能なマスまでの移動回数を求めます。その中で最も大きい移動回数となる値が今回の答えです。これはBFSを使用して、スタート地点の全探索をすることでもとめることができます。計算量はO((HW)2)なので、十分間に合います。

実装

実装の全体

実装の全体は下記に乗せておきます。 github.com

ハマったポイント

過去の記事では、BFSの実装はスタートとゴールの座標情報を引数として渡していたので、スタートとゴールの組み合わせをfor文で実装していた(for文の4重構造)のですが、これはTLEしました。

そもそも、幅優先探索では、

  • 1回の移動で行けるところを確定
  • 2回の移動で行けるところを確定
  • 3回の移動で行けるところを確定....

と近い場所から確定していくので、BFSを最後まで処理して、その時の値を返せば自ずとスタートに対して最も遠いゴールまでの移動回数を求めることができます。つまり、スタート地点の全探索で、各スタートにおける最も遠いゴールまでの移動回数を求めて、さらにその中でも最大値を答えにすればOKです。