문제 설명

N×M 크기의 방에 로봇 청소기가 있습니다. 로봇은 다음 규칙에 따라 움직입니다: 1. 현재 칸이 청소되지 않았으면 청소한다. 2. 현재 방향 기준 왼쪽부터 탐색: - 왼쪽에 청소하지 않은 빈 칸이 있으면 회전 후 전진 - 없으면 계속 왼쪽으로 회전 3. 4방향 모두 청소했거나 벽이면: - 후진 가능하면 후진 후 2번으로 - 후진 불가(벽)이면 작동 종료 로봇이 청소하는 칸의 개수를 구하세요.

입력

출력

제약 조건

• •3 <= N, M <= 50
• •방향 d: 0(북), 1(동), 2(남), 3(서)
• •처음 로봇 위치는 항상 빈 칸

예제

3 3
1 1 0
1 1 1
1 0 1
1 1 1

1

4 4
1 1 0
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

4