규칙에 따라 시작점에서 시작하여 파이프를 반대쪽 모서리까지 옮기는 경우의 수를 구하는 문제입니다. 가능한 방향은 오른쪽, 오른쪽 아래, 아래의 세 방향이고 한 번 옮길 때마다 방향을 45도까지만 전환할 수 있습니다. 이 경우를 일일이 다 찾을 수는 없기 때문에 특정 칸에 파이프 끝이 존재할 때 방향마다 가능한 경우의 수를 시작점부터 시작하여 끝점까지 저장해나가면 됩니다. 이 때 주의해야할 점은 가로 또는 세로로 이동하는 경우 이동할 칸만 비었는지 체크하면 되지만 대각선으로 움직일 때에는 이동할 칸과 그 위, 왼쪽 칸 또한 비었는지 체크해야한다는 것입니다. 이제 규칙에 따라 DP 배열을 구성하여 끝 점에 도달할 수 있는 경우의 수를 구하면 됩니다.
여기서 팁은 열의 번호가 2 이하인 점은 구할 필요가 없다는 것입니다. 가능한 경우의 수가 없기 때문입니다. 따라서 (1, 3)에서 (n, n)까지만 구하면 됩니다.
PS알못 OrbitHv의 PS