개구리의 여행

어떤 호수에 개구리 한마리가 살고 있습니다. 이 개구리는 여행을 무척 좋아합니다.

호수에는 N×N 크기의 정사각형 형태로 돌이 있으며, 개구리는 돌 위에서 돌아다닐 수 있습니다. 각 돌의 위치는 좌표로 표현할 수 있는데, 위에서부터 i번째, 왼쪽부터 j번째 위치를 (i, j)로 표현합니다. 따라서 가장 왼쪽 위에 있는 돌의 좌표는 (1, 1)이며 가장 오른쪽 아래에 있는 돌의 좌표는 (N, N)입니다.

개구리가 모든 위치를 자유롭게 돌아다닐 수 있다면 좋겠지만, 안타깝게도 이 호수에는 개구리가 갈 수 없는 위험한 돌도 있습니다.