C: Fountain Walk - AtCoder Grand Contest 019
格子マップ及びいくつかの頂点が与えられる。格子の辺は100m、与えられた頂点にはN個の噴水があり、半径10mの外周を通ることが可能である。格子点は同一水平線上または同一垂直線上にたかだか1個である。
スタートとゴールが与えられたときに、最短経路を答えよ。
まず分かることは角を曲がる時噴水を通ると、普通に格子点で曲がったときよりも距離が短くなり、噴水を縦または横に通り過ぎると格子点を直進するときよりも距離が長くなる。なので、なるべく格子点を曲がるときに通るのがよい。ここで、同一直線状に噴水はたかだか1個しかないことから、ゴールとスタートの間のマス目のサイズををH*Wとすると、min(H, W) + 1個しか存在しないことになる。まずはこの区間にある噴水をできるだけ通ることを考える。そこで区間内の噴水をx方向にソートする。その上で、噴水のy座標の最長増加列を計算すると、その列に含まれる噴水はゴールまでに通ることが可能である。この最長増加列の個数をkと置く。
k < min(H, W) + 1 のとき、全て曲がり角として噴水を通ることが可能なので、その差分を通常の格子点の最短経路(w + h)*100から引けばよい。
k = min(H, W) + 1のとき、最低でも1個は噴水を横切ってしまう。なのでその差分を足しておく。
全体でO(N)。
