TPC追いコン A 不完全迷路
問題概要
高さ 幅
の迷路が与えられる。
壁のマスを1マスのみ道のマスに変えたとき、スタートのマスからゴールのマスへの最短経路長が最長となるようにしたい。
そのときのスタートからゴールまでの最短経路長を求めよ。
制約
TLE解法
それぞれの壁のマスに対し、そのマスを道に変えたときのスタートからゴールまでの最短経路をすべて求めて、その最大値を出力する。
計算量は になる。
解法
ある壁のマスを道に変えたとき、そのマスを通るスタートからゴールまでの最短経路長は、
（そのマスの上下左右どれかのマスの、スタートからの最短経路長）（そのマスの上下左右どれかのマスの、ゴールからの最短経路長）
であることがわかる。
また、変更するマスは1つのみなので、「そのマスの上下左右どれかのマスの、スタートからの最短経路長」と「そのマスの上下左右どれかのマスの、ゴールからの最短経路長」は、与えられた迷路から求めることができる。
与えられた迷路の道のマスすべてについて、スタートからとゴールからの最短経路長を前計算しておき、それぞれの壁のマスに対し、そのマスを道に変えたときのスタートからゴールまでの最短経路を求めて、最大値を出力する。
この場合、計算量は になる。
