ABC258 F - Main Street (500)
コンテスト中の考察
大通りに囲まれている部分を区画とする
区画内の最短距離になり得るケースは7パターン
本当は13パターンある気がする
4パターンに分類する
同じく区画の場合
単に区画内の最短距離を求める
縦または横が等しい区画の場合
相手の区画の方にある角のいずれかを双方で目指し、その間は大通りを使う
これは角が2つずつあるので4通り
それ以外
相手の区画の方にある角がそれぞれ1個なので双方でそこを目指し、その間は大通りを使う
解説の解法
それぞれの地点から大通りに出た場合の位置とコストをそれぞれ4パターン求める
大通りを使わない場合を暫定の答えにする
大通りを使った場合の4パターン同士を組み合わせて以下を行う
これらの点は全て大通り上
この点の間について大通りだけを使う場合と使わない場合について最小値を求めて答えを可能なら更新する