중력 뒤집기

보비디안 선장은 동료인 비팔로 박사를 구하기 위해 모험을 떠났습니다. 이 세계는 선장이 사는 세상을 옆에서 바라본 $N \times M$ 크기의 2차원 격자($1 \le N, M \le 500$)로 나타냅니다. 격자의 각 칸은 비어 있거나, 막혀 있어 지나갈 수 없습니다.

보비디안 선장은 점프할 수 없으며, 세계를 이동하는 동안 다음과 같은 물리 법칙을 반드시 따라야 합니다.

1. 선장의 바로 아래에 칸이 없다면(즉, 중력 방향으로 격자의 끝에 있다면) 선장은 우주 밖으로 날아가 임무에 실패합니다.
2. 선장의 바로 아래 칸이 비어 있다면 선장은 그 칸으로 떨어집니다.
3. 그 외의 경우(바로 아래 칸이 막혀 있는 경우) 선장은 다음 중 하나를 할 수 있습니다. a. 해당 칸이 존재하고 비어 있다면 왼쪽 또는 오른쪽으로 한 칸 이동합니다. b. 또는 중력의 방향을 뒤집습니다.

선장이 중력의 방향을 뒤집으면, 규칙 1과 2에서 말하는 "아래"의 의미가 행 번호가 $1$ 큰 칸과 $1$ 작은 칸 사이에서 서로 바뀝니다. 첫 번째 행의 번호는 $1$이고 마지막 행의 번호는 $N$입니다. 처음에는 행 번호가 $1$ 큰 칸이 선장의 "아래" 칸입니다.

비팔로 박사는 이 세계 어딘가에 갇혀 있습니다. 중력을 뒤집는 횟수를 최소로 하여 선장이 박사가 있는 칸에 도달하도록 도와주세요. 박사에게 도달할 수 없다면 $-1$을 출력합니다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄은 선장 세계의 $i$번째 행을 나타냅니다. .은 빈 칸, #은 막힌 칸, C는 보비디안 선장의 시작 칸, D는 비팔로 박사가 있는 칸을 뜻합니다. C와 D는 각각 정확히 하나씩 있으며, 둘 다 빈 칸 위에 있습니다.

• 첫째 줄: 보비디안 선장이 비팔로 박사에게 도달하기 위해 중력을 뒤집어야 하는 최소 횟수를 출력합니다. 도달할 수 없다면 $-1$을 출력합니다.

예시 설명

보비디안 선장은 $(4, 2)$(4행 2열)에서 시작합니다. 중력을 뒤집어 $(2, 2)$로 떨어진 뒤, 오른쪽으로 두 번 이동해 $(2, 4)$에 도착합니다. 다시 중력을 뒤집어 $(4, 4)$로 떨어진 뒤, 오른쪽으로 한 번 이동해 $(4, 5)$로 갑니다. 마지막으로 중력을 한 번 더 뒤집어 $(3, 5)$에 있는 비팔로 박사에게로 떨어집니다. 중력을 뒤집은 횟수는 모두 세 번입니다.