아기 고래의 첫 항해

넓은 바다에 갓 태어난 아기 고래 한 마리가 있습니다. 아기 고래는 엄마 고래로부터 독립하여 처음으로 넓은 바다를 탐험하려 합니다.

바다는 N×N 크기의 격자로 표현됩니다. 격자의 각 칸은 헤엄칠 수 있는 바다(0)이거나, 지나갈 수 없는 암초(1)입니다. 격자에서 i행 j열의 칸을 (i,j)로 표현합니다.

아기 고래는 위치 (r,c)에서 출발하며, 처음에 바라보는 방향은 d입니다. 방향은 1이 상, 2가 하, 3이 좌, 4가 우를 의미합니다.