위로 이동할 수 없으므로 한 행에서 아래 행으로 내려가면 이전 행으로 돌아오지 않는다. 한 행 안에서 가로 이동 방향을 바꾸면 바로 전에 방문한 칸을 다시 방문하게 된다. 따라서 각 행에서는 한 방향으로만 가로 이동할 수 있다.
직전 이동 방향만 저장하면 충분하지 않다. 직전 이동이 아래쪽이었다면 그 한 번 전의 이동이 오른쪽이었는지, 왼쪽이었는지에 따라 다음 가로 이동의 허용 여부가 달라진다. 다음 다섯 상태로 이를 구분한다.
아직 이동하지 않은 출발점도 상태로 취급한다. 처음 아래로 이동한 경우 역시 상태가 된다.
를 에 상태 로 도착하는 유효한 경로의 최대 이동 거리로 정의한다. 도달할 수 없는 상태는 로 둔다. 처음에는 이고 나머지 상태는 모두 도달할 수 없다. 벽과 격자 밖의 상태도 모두 도달할 수 없는 것으로 취급하며, 도달할 수 없는 값에 을 더해 새로운 경로를 만들지 않는다.
먼저 바로 위 칸에서 내려오는 경우를 계산한다. 마지막 이동이 가로 방향이면 그 방향을 한 번 더 기억하고, 이미 아래로 이동한 상태였다면 가로 방향에 따른 제한이 사라진다.
이 식은 인 이동 가능한 칸에 적용한다. 출발점의 초기값은 그대로 유지한다.
오른쪽으로 이동할 때에는 이전 상태가 , , 중 하나여야 한다. 에서 방향을 바꾸면 이미 방문한 칸으로 돌아가고, 에서 오른쪽으로 이동하면 금지된 세 번의 이동이 만들어지기 때문이다. 따라서
이다. 대칭적으로 왼쪽 이동은
로 계산한다.
각 행에서 아래로 도착하는 세 상태를 먼저 모두 계산한다. 이어서 왼쪽부터 오른쪽으로 훑으며 상태를 계산하고, 오른쪽부터 왼쪽으로 훑으며 상태를 계산한다. 두 가로 방향의 상태끼리는 전이하지 않으므로 이 순서로 모든 점화식을 계산할 수 있다. 각 행을 시작할 때 새 행의 상태를 모두 도달 불가능으로 초기화하고, 벽에서는 어떤 상태도 갱신하지 않는다.
도착점의 다섯 상태 중 최댓값을 출력한다. 모두 도달 불가능이면 을 출력한다. 처음부터 이동 거리를 저장했으므로 방문한 칸 수를 거리로 변환할 필요는 없다.
각 칸에서 일정한 수의 상태를 계산하므로 시간 복잡도는 이다. 이전 행과 현재 행의 상태만 저장하고 격자도 한 행씩 처리하면 공간 복잡도는 이다.
증명
유효한 경로는 위로 이동하지 않으므로 각 행에 최대 한 번 들어온다. 한 행에서 왼쪽과 오른쪽 이동을 모두 한다면 처음으로 가로 방향을 바꾸는 순간 바로 전에 방문한 칸으로 돌아가게 된다. 따라서 한 행에서의 가로 이동은 한 방향뿐이다. 새 행으로 내려갈 때에는 아직 방문하지 않은 칸으로 이동하고, 같은 방향으로 가로 이동할 때에도 아직 방문하지 않은 칸으로 이동한다. 점화식은 같은 행의 반대 가로 방향 상태로부터 전이하지 않으므로 재방문을 만들지 않는다.
오른쪽으로 이동하기 전의 상태는 , , 일 때만 허용된다. 은 재방문을 만들고 은 왼쪽, 아래쪽, 오른쪽이라는 금지된 이동을 만든다. 왼쪽 이동도 대칭적으로 정확히 , , 에서만 허용된다. 아래 이동은 항상 이동 방향에 관한 제한을 만족하며, 이전 상태가 이면 , 이면 , 나머지이면 가 된다. 따라서 점화식에 포함된 전이는 모두 유효하고, 모든 유효한 경로의 마지막 이동은 이 전이들 중 하나이다.
Solution written by GPT6
각 행의 아래 방향 상태는 이전 행의 상태만 사용한다. 상태는 같은 행의 왼쪽 상태만, 상태는 오른쪽 상태만 사용하므로 제시한 계산 순서는 모든 선행 상태를 먼저 계산한다. 출발점의 값은 정확하며, 이미 계산한 선행 상태의 최댓값에 한 번의 이동 거리를 더하면 각 상태의 정의를 유지한다. 귀납적으로 모든 상태가 해당 상태로 끝나는 가장 긴 유효한 경로의 거리를 저장한다. 그러므로 도착점에서의 최댓값이 정답이며, 도달 가능한 상태가 없다면 유효한 경로도 없다.
