Mujin Programming Challenge 2018 C - 右折
解法
最初に右を向いていて,次に右折するパターンを考える.
各マスで上方向に累積和をとると下に何マス進めるかというのがO(NM)でわかる.
それを左方向に累積和をとっていくとその場所を始点として1マス以上進み,右に何マス進めるかというのがわかるのでこのパターンは解けた.
これを全方向実装するのはかなりめんどくさいので,迷路自体を回転してループを4回回せばいい.
メモ
公式解答は鮮やかすぎて思いつかないので...
最初に右を向いていて,次に右折するパターンを考える.
各マスで上方向に累積和をとると下に何マス進めるかというのがO(NM)でわかる.
それを左方向に累積和をとっていくとその場所を始点として1マス以上進み,右に何マス進めるかというのがわかるのでこのパターンは解けた.
これを全方向実装するのはかなりめんどくさいので,迷路自体を回転してループを4回回せばいい.
公式解答は鮮やかすぎて思いつかないので...