2026-10-13
Estimate.hs
estimate :: [(Int, Int)] -> (Int, Int) -> Int
上下左右に1マスずつ動くグリッドで、位置 (x, y) から goals のうちいちばん近い目的地までの見積もりを返す estimate を書いてください。見積もりは、各目的地とのマンハッタン距離(x 座標の差の絶対値と y 座標の差の絶対値の和)のうち最小のものです。goals は空でないものとし、目的地の上にいるときは0を返します。
入力例 1
estimate [(0, 0)] (3, 4)
出力例 1
7
入力例 2
estimate [(0, 0), (5, 5)] (4, 3)
出力例 2
3
入力例 3
estimate [(2, 2)] (2, 2)
出力例 3
0
Reference
estimate :: [(Int, Int)] -> (Int, Int) -> Int
estimate goals (x, y) = minimum [abs (x - gx) + abs (y - gy) | (gx, gy) <- goals]
リスト内包表記で各目的地とのマンハッタン距離を並べ、minimum で最小のものを取ります。入力例2では (0, 0) までが7、(5, 5) までが3なので、3が返ります。
上下左右に1マスずつしか動けないなら、どの目的地へ行くにも、少なくともマンハッタン距離だけの歩数が要ります。壁があれば実際の歩数はもっと増えますが、見積もりが実際を超えない限り、A*探索はこの値を使っても最短経路を見つけられます。目的地が複数あるときは、いちばん近いものまでの距離を取れば、どの目的地に着く経路と比べても実際を超えません。
minimum は空リストではエラーになるので、goals が空でないことを前提にしています。掲載したのは参考実装で、唯一の正解ではありません。距離を求める関数を where で分けて minimum (map dist goals) と書いても同じです。