メモ化再帰で解いた。 dp[i][j][p]:=現在(i,j)にいて、状態pである。i…南北 j…東西p= 1…直前に曲っていて、東に進んでいる →東に進み、p=32…直前に曲っていて、北に進んでいる →北に進み、p=43…直前に曲っていない、東に進んでいる →東に進み、p=3 または 北…