What's Up With Gravity

Captain Bovidian is on an adventure to rescue her crew member, Doctor Beefalo. Like all great adventures, this story plays out on a two-dimensional $N \times M$ grid ($1 \le N, M \le 500$) that represents a side view of the captain's world. Some grid cells are empty, while others are blocked and cannot be entered.

Captain Bovidian cannot jump. As she moves through her world she must obey the following rules of physics:

1. If there is no cell directly underneath her (that is, she is at the edge of the grid in the direction of gravity), she flies off into space and the mission fails.
2. If the cell directly underneath her is empty, she falls into that cell.
3. Otherwise (the cell directly underneath her is blocked), she may either: a. move one cell left or right, provided that cell exists and is empty, or b. flip the direction of gravity.

When Captain Bovidian flips the direction of gravity, the meaning of "underneath" (used in rules 1 and 2) toggles between the cell with one higher row index and the cell with one lower row index. The first row has index $1$ and the last row has index $N$. Initially, the cell with one higher row index is the cell underneath her.

Doctor Beefalo is stranded somewhere in this world. Help Captain Bovidian reach his cell using as few gravity flips as possible. If it is impossible to reach Doctor Beefalo, output $-1$.

• Line 1: two space-separated integers $N$ and $M$.
• Lines 2 to $N+1$: line $i+1$ describes the $i$-th row of the captain's world. . is an empty cell, # is a blocked cell, C is Captain Bovidian's starting cell, and D is Doctor Beefalo's cell. There is exactly one C and exactly one D, and both occupy otherwise-empty cells.

• Line 1: a single integer — the minimum number of times Captain Bovidian must flip gravity to reach Doctor Beefalo, or $-1$ if it is impossible.

About the example

Captain Bovidian starts at position $(4, 2)$ (row 4, column 2). She flips gravity and falls to $(2, 2)$, then moves right twice to $(2, 4)$. She flips gravity again and falls to $(4, 4)$, then moves right once to $(4, 5)$. Finally she flips gravity a third time and falls onto Doctor Beefalo at $(3, 5)$. Three flips in total.