스케이트

Natalie는 새 스케이트를 샀고, 동네 스케이트장에서 시험해 보기로 했다. 스케이트장은 직사각형 모양이며, 그 위에는 여러 장애물이 배치되어 있다. Natalie는 링크의 서쪽에 있으며, 이제 반대편인 동쪽으로 건너가고자 한다.

Natalie는 스케이트를 그다지 잘 타지 못한다. Natalie가 입구를 통해 빙판에 들어가면 장애물에 부딪힐 때까지 방향을 바꿀 수 없다. 첫 번째 장애물에 부딪히면 왼쪽이나 오른쪽으로 방향을 바꾼 뒤 다시 직진할 수 있으며, 이후에도 같은 방식으로 움직인다. 즉, 장애물에 부딪힐 때마다 항상 왼쪽이나 오른쪽으로 90도 방향을 바꾸며, 장애물에 부딪혔을 때만 방향을 바꿀 수 있다.

Natalie는 이 이동을 최대한 간단하게 하고 싶어 한다. 빙판의 오른쪽인 동쪽으로 빠져나가기 위해 방향을 바꿔야 하는 최소 횟수는 얼마인가? Natalie는 항상 맨 왼쪽 위 칸을 통해 빙판에 들어오며, 처음에는 동쪽인 오른쪽으로 이동한다.

점수

당신의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

1 | 40 | $3 \le R,C \le 15$

2 | 30 | $3 \le R,C \le 30$

3 | 30 | $3 \le R,C \le 100$

첫째 줄에는 정수 $R$과 $C$이 공백 하나로 구분되어 주어진다.

다음 $R$개의 줄은 각각 스케이트장의 각 칸이 어떤 상태인지를 나타내는 $C$개의 문자로 이루어진다. '.'는 빈 칸을 의미하며, '#'는 장애물이 있는 칸을 나타낸다.

Natalie가 링크의 오른쪽으로 빠져나가면 이동을 마친다. 링크의 다른 쪽(위쪽, 아래쪽 또는 왼쪽)으로 빠져나가면 목표 달성에 실패한다. Natalie는 항상 $(0,0)$ 칸에서 시작하여 오른쪽으로 이동한다.

프로그램은 Natalie가 빙판의 오른쪽으로 빠져나가기 위해 방향을 바꿔야 하는 최소 횟수를 한 줄에 출력해야 한다. 해답이 존재함이 보장된다.

세 번째 예제(예제 입력 3)에서 Natalie는 먼저 첫 번째 장애물까지 동쪽으로 이동한다. 그런 다음 오른쪽으로 방향을 바꾸고 아래쪽으로 이동한다. 이어서 다시 오른쪽으로 방향을 바꾸고 서쪽으로 이동한 뒤, 마지막으로 오른쪽으로 두 번 더 방향을 바꾸어 빙판의 동쪽 가장자리에 도달한다. 방향을 바꾼 횟수는 모두 네 번이므로 답은 네 번이다.