USACO 2013 US Open, Silver
Problem 1. What's Up With Gravity
Contest has ended.
Log in to allow submissions in analysis mode
Problem 1: What's Up With Gravity? [Mark Gordon, 2013]
Captain Bovidian is on an adventure to rescue her crew member, Doctor
Beefalo. Like all great adventures, 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 while traversing her world.
1) If there is no cell directly underneath Captain Bovidian (that is, if
she is at the edge of the grid), then she flies out into space and fails
her mission.
2) If the cell directly underneath Captain Bovidian is empty, then she
falls into that cell.
3) Otherwise:
a) Captain Bovidian may move left or right if the corresponding cell
exists and is empty.
b) Or, Captain Bovidian may flip the direction of gravity.
When Captain Bovidian changes the direction of gravity, the cell that's
'underneath' her (as mentioned 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 in the input has index 1, and the last row has index N). Initially, the
cells with one higher row index are underneath Captain Bovidian.
Doctor Beefalo is lost somewhere in this world. Help Captain Bovidian
arrive at her cell using the least number of gravity flips as possible. If
it is impossible to reach Doctor Beefalo, please output -1.
PROBLEM NAME: gravity
INPUT FORMAT:
* Line 1: Two space-separated integers N and M.
* Lines 2..1+N: Line i+1 describes the ith row of Captain Bovidian's
world: '.' indicates an empty cell, '#' indicates a blocked
cell, 'C' indicates Captain Bovidian's starting position, and
'D' indicates Doctor Beefalo's starting position.
SAMPLE INPUT (file gravity.in):
5 5
#####
#...#
#...D
#C...
##.##
OUTPUT FORMAT:
* Line 1: A single integer indicating the minimum number of times
Captain Bovidian must flip gravity to reach Doctor Beefalo, or
-1 if it is impossible to reach Doctor Beefalo.
SAMPLE OUTPUT (file gravity.out):
3
OUTPUT DETAILS:
The captain starts at position (4, 2). She flips gravity and falls to
position (2, 2) and then moves right twice to arrive at (2, 4). She flips
gravity again and falls to position (4, 4) and then moves right once to
position (4, 5). Finally she flips gravity again to fall to Doctor
Beefalo's position at (3, 5).
Contest has ended. No further submissions allowed.