Namaran

Code daily. Without assist.

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) と書いても同じです。