양 몽유병 timer 20s memory 1024MB

블레이트릭스 트로터(Bleatrix Trotter)는 2차원 들판에 사는 양으로, 그 들판은 한 변의 길이가 1인 칸들로 이루어진 무한한 격자이다. 블레이트릭스의 집은 (0, 0)으로 표시되는 칸에 있으며, 모든 좌표는 블레이트릭스의 집을 기준으로 한다. 하지만 몽유병 때문에, 지금 블레이트릭스는 좌표가 (X, Y)인 칸에 있다. 즉, 집에서 동쪽으로 X칸, 북쪽으로 Y칸 떨어진 칸이다. 블레이트릭스를 보호하도록 배정된 두 마리의 양치기개가 양이 사라진 것을 방금 알아차렸고, 이제 블레이트릭스를 집으로 몰아가려 한다.

블레이트릭스가 한 번 움직이기 전에, 두 양치기개는 원하는 어떤 격자 칸으로든 이동할 수 있다. 단, 두 마리가 같은 칸으로 이동할 수는 없고, 어느 쪽도 블레이트릭스가 현재 있는 칸으로 이동할 수도 없다. 양치기개들이 자리를 잡고 나면, 몽유병에 걸린 블레이트릭스는 양치기개가 있는 칸으로 들어가지 않는 방향으로 길이 1의 무작위 이동을 한다. 즉, 가능한 네 방향 이동(북/남/서/동) 중에서 양치기개가 있는 칸으로 들어가게 되는 이동은 모두 버리고, 남은 이동들 중에서 균등한 확률로 하나를 선택한다. 그 다음 다시 양치기개들이 위치를 정할 수 있고, 이 과정을 반복한다. (블레이트릭스와 달리, 양치기개들은 한 번에 한 칸씩 이동할 필요가 없다는 점에 유의하라.)

블레이트릭스가 집이 있는 (0, 0)에 도착하면, 몽유병이 멈추고 깨어나서 평화롭게 풀을 뜯으며, 그 이후로는 더 이상 움직이지 않는다.

두 양치기개가 블레이트릭스가 집에 도착하기까지의 이동 횟수의 기댓값을 최소화하도록 협력한다면, 그 기댓값은 얼마인가?