마법의 숲 탐색

정령들이 R행 C열의 격자 형태로 이루어진 마법의 숲을 탐색하려고 합니다. 격자는 가장 위를 1행, 가장 아래를 R행으로 합니다.

숲의 동쪽, 서쪽, 남쪽은 마법의 벽으로 막혀 있으며, 정령들은 숲의 북쪽을 통해서만 숲에 들어올 수 있습니다.

총 K명의 정령은 각자 골렘을 타고 숲을 탐색합니다. 각 골렘은 십자 모양의 구조를 가지고 있으며, 중앙 칸을 포함해 총 5칸을 차지합니다. 골렘의 중앙을 제외한 4칸 중 한 칸은 골렘의 출구입니다. 정령은 어떤 방향에서든 골렘에 탑승할 수 있지만 골렘에서 내릴 때에는 정해진 출구를 통해서만 내릴 수 있습니다.