[swat]애벌레 키우기3 timer 1s memory 512MB

정올이는 애벌레를 키우다보니 애벌레가 매우 크게 자라서 왕벌레가 되었고 이제 작은 벌레들을 먹이로 주기로 했다.

정올이는 기왕이면 먹이를 통해 왕벌레를 훈련시키기 위해 4 * 4의 격자판에 각 칸마다 한마리씩의 벌레들을 올려놓고 계속 움직이면서 서로 위치를 바꾸도록 하였다.

격자판의 위치는 행과 열의 좌표로 표시하며 왼쪽 위는 (0, 0)이고 오른쪽 아래는 (3, 3)이다.

벌레들은 각각 1부터 16까지 서로 다른 번호로 표시가 되어 있으며 처음에는 각각 상하좌우 및 대각선의 8방향중 한 곳으로 향하고 있다.

왕벌레는 처음에 (0, 0)에 놓아주면 그 위치에 있는 벌레를 잡아먹고 그 자리에 있던 벌레의 방향으로 서게 된다.

벌레를 한 마리 잡아먹을 때마다 아직 남아있는 벌레들은 모두 이동을 하게 되는데 이동하는 규칙은 다음과 같다.

1) 번호가 작은 벌레부터 모든 벌레가 이동을 한다.

2) 이동은 벌레가 현재 서 있는 방향으로 한 칸을 앞으로 전진하는데 이동하려는 위치가 비어있다면 그대로 가면 되지만, 만약 그 자리에 다른 벌레가 있다면 자리를 바꾸게 된다.

3) 만약 이동하려는 위치로 이동 할 수 없다면 (격자판의 범위를 벗어나거나 그 자리에 왕벌레가 있다면) 이동이 가능할 때까지 왼쪽으로 45도씩 방향을 바꾼다.

4) 이동을 하고 나서는 지금 이동한 방향을 그대로 유지한다.

벌레들의 이동과정은 아래의 도움말을 참조하라.

이동이 모두 끝나면 이제 왕벌레가 자기가 서 있는 방향으로 전진해서 다른 벌레를 잡아 먹을 수 있다. 

왕벌레는 여러칸을 한꺼번에 이동할 수는 있지만 이동하면서 벌레를 잡아먹을 수는 없고 이동이 끝난 후 멈춘 칸의 벌레만 잡아 먹게 된다.

범위를 벗어나거나 벌레가 없는 빈 칸으로는 이동을 할 수 없고 만약 이동 할 수 있는 곳이 없다면 훈련을 끝내게 된다.

훈련이 끝날 때까지 왕벌레가 잡아 먹은 벌레들의 번호의 합이 최대가 되도록 할 때 그 합을 출력하는 프로그램을 작성하라.