로봇 청소기

로봇 청소기와 방의 상태가 주어질 때, 로봇 청소기가 청소하는 칸의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 $N \times M$ 크기의 직사각형이고, $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각 칸은 벽이거나 빈 칸이다. 청소기에는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 $(r, c)$로 나타낸다. 가장 북쪽 줄의 가장 서쪽 칸이 $(0, 0)$이고, 가장 남쪽 줄의 가장 동쪽 칸이 $(N-1, M-1)$이다. 즉 좌표 $(r, c)$는 북쪽에서 $(r+1)$번째 줄의 서쪽에서 $(c+1)$번째 칸이다. 처음에는 모든 빈 칸이 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않았으면 현재 칸을 청소한다.

2. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 없으면,

   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

3. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 있으면,

   1. 반시계 방향으로 $90^\circ$ 회전한다.
   2. 바라보는 방향 기준으로 앞쪽 칸이 청소되지 않은 빈 칸이면 한 칸 전진한다.
   3. 1번으로 돌아간다.

첫째 줄에 방의 크기 $N$과 $M$이 주어진다. $(3 \le N, M \le 50)$

둘째 줄에 로봇 청소기가 처음 있는 칸의 좌표 $(r, c)$와 처음 바라보는 방향 $d$가 주어진다. $d$가 $0$이면 북쪽, $1$이면 동쪽, $2$이면 남쪽, $3$이면 서쪽을 바라본다.

셋째 줄부터 $N$개의 줄에 걸쳐 각 칸의 상태를 나타내는 값이 한 줄에 $M$개씩 주어진다. $i$번째 줄의 $j$번째 값은 칸 $(i, j)$의 상태이다. 이 값이 $0$이면 $(i, j)$는 청소되지 않은 빈 칸이고, $1$이면 $(i, j)$에 벽이 있다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 속한 칸에는 모두 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

로봇 청소기가 작동을 시작한 뒤 멈출 때까지 청소하는 칸의 개수를 출력한다.