중력 변경

선장 루피는 선원 닥터 쵸파를 구하기 위한 모험을 떠나고 있습니다. 이 위대한 모험이야기는 N x M 크기의 2차원 그리드 (1 <= N, M <= 500)에서 펼쳐집니다. 이 그리드는 세계의 측면 모습을 나타냅니다. 일부 그리드 셀은 비어 있으며, 다른 셀은 막혀 있어 이동할 수 없습니다.

불행히도, 캡틴 루피는 점프할 수 없습니다. 세계를 건너갈 때 다음의 물리 법칙을 지켜야 합니다.

1) 만약 캡틴 루피 바로 아래에 셀이 없다면 (즉, 그가 격자의 가장자리에 있다면), 그는 우주 공간으로 날아가 임무는 실패합니다. 

2) 만약 캡틴 루피 바로 아래의 셀이 비어있다면, 그는 그 셀로 떨어집니다. 

3) 그 외의 경우: 

• a) 캡틴 루피는 좌우로 움직일 수 있습니다. 이 때, 해당 칸이 존재하고 비어있어야합니다. 
• b) 또한, 캡틴 루피는 중력의 방향을 뒤집을 수 있습니다.

캡틴 루피가 중력의 방향을 바꾸면, 그의 밑에 있는 셀 (규칙 1과 2에서 언급한 '아래'의 셀)이 한 쪽 높은 행 인덱스의 셀과 한 쪽 낮은 행 인덱스의 셀 사이를 전환합니다. (입력의 첫 행은 인덱스 1을 가지고, 마지막 행은 인덱스 N을 가지고 있습니다.) 초기에는, 한 쪽 높은 행인덱스를 가진 셀들이 캡틴 루피 아래에 있습니다.

닥터 쵸파는 이 세계 어딘가에 분실되었습니다. 캡틴 루피가 가장 적은 중력 뒤집기 수로 그의 셀에 도달 할 수 있도록 도와주세요. 만약 닥터 쵸파에게 도달하는 것이 불가능하다면, -1을 출력해 주세요.

• 첫 번째 줄: 공백으로 구분된 두 정수 N 과 M.
• 두 번째 줄..1+N 번째 줄 : i+1번째 줄이 캡틴 루피의 세계의 i 번째 행을 기술합니다: '.' 는 비어 있는 셀을 나타내고, '#' 는 차단된 셀을 나타내고, 'C' 는 캡틴 루피의 시작 위치를 나타내고, 그리고 'D' 는 닥터 쵸파의 시작 위치를 나타냅니다.

• 첫 번째 줄: 캡틴 루파가 닥터 쵸파에게 도달하기 위해 중력을 뒤집어야하는 최소 횟수를 나타내는 단일 정수, 또는 닥터 쵸파에게 도달하는 것이 불가능한 경우 -1.