Captain Bovidian is on an adventure to rescue her crew member, Doctor Beefalo. This story plays out in a two dimensional N by M grid (1 <= N, M <= 500), representing a side view of the captain's world. Some grid cells are empty while others are blocked and cannot be traversed.

Unfortunately, Captain Bovidian cannot jump. She must obey the following rules of physics:

1) If there is no cell directly underneath Captain Bovidian (she is at the edge of the grid), then she flies out into space and fails.
2) If the cell directly underneath her is empty, then she falls into that cell.
3) Otherwise: (a) she may move left or right if the corresponding cell exists and is empty; or (b) she may flip the direction of gravity.

When she changes the direction of gravity, the cell that is 'underneath' her toggles between the cell with one higher row index and the cell with one lower row index (the first row has index 1, the last row index N). Initially, the cells with one higher row index are underneath her.

Help Captain Bovidian reach Doctor Beefalo using the least number of gravity flips. If it is impossible, output -1.

Line 1: Two space-separated integers N and M.

Lines 2..1+N: Line i+1 describes the ith row: '.' indicates an empty cell, '#' a blocked cell, 'C' Captain Bovidian's starting position, and 'D' Doctor Beefalo's starting position.

A single integer indicating the minimum number of times Captain Bovidian must flip gravity to reach Doctor Beefalo, or -1 if it is impossible.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > US Open > Silver