Description
PIPI and his friend POPO are lost in Central South University, and they both hope to find each other as soon as possible.
PIPI can move twice per second, each time he can move to another space in four directions: up / down / left / right. POPO can move once per second, and each time he can move to another space in eight directions : up / down / left / right / top right / bottom right / top left / bottom left.
How many seconds does it take for PIPI and POPO to meet each other? Give the minimum time.
Input
The first row is two integers N and M(1<=N,M<=1000), representing the rows and columns of the map.
Next is an N × M matrix.
Among them, "D" indicates the position of PIPI, and "C" indicates the position of POPO.
"#" Indicates an obstacle that cannot be passed, and "." Is a position that can pass normally.
Output
If they can meet each other, the first line outputs a YES, and the second line outputs the minimum encounter time.
Otherwise, a NO is output to indicate that they cannot meet each other.
Sample Input
4 5
.....
.###.
...#D
..C#.
