はじめに

今回提出した方法のおおまかな解説です。

短く拙い文章ですがご了承ください。

家と水源間の水路の通し方

家と水源間の中継点を求め、家と中継点間、中継点と水源間で同様に中継点を求めるという操作を再帰的に行うことで家と水源をつなげるということを行いました。

コードの形で書くと以下のようになります。

function rec(start, goal)

    # 2点間の距離が一定以下なら掘削してつなげる
    if dist(start, goal) < THRESHOLD
        excavate(start, goal)
        return
    end

    # 中継点の候補を列挙
    candidates = get_candidates(start, goal)
    # 候補点からベストな点を選ぶ
    selected_point = select_point(candidates)


    rec(start, selected_point)
    rec(selected_point, goal)
end

rec(start, goal)

中継点の候補はstart(家), goal(水源)から等距離の線上からいくつか選びました。

あとはこの方法をベースとして細かい改善を加えていきました。