레이팅 미적용보비디언 선장은 승무원인 비팔로 박사를 구출하기 위한 모험을 떠났다. 이 이야기는 선장의 세계를 옆에서 본 모습을 나타내는 2차원 N x M 격자 (1 <= N, M <= 500)에서 펼쳐진다. 어떤 격자 칸은 비어 있고, 다른 칸은 막혀 있어 지나갈 수 없다.
안타깝게도 보비디언 선장은 점프를 할 수 없다. 선장은 다음 물리 법칙을 따라야 한다.
1) 보비디언 선장 바로 아래에 칸이 없으면(격자의 가장자리에 있으면), 선장은 우주로 날아가 버려 실패한다.
2) 바로 아래 칸이 비어 있으면, 그 칸으로 떨어진다.
3) 그 외의 경우: (a) 해당 칸이 존재하고 비어 있으면 왼쪽 또는 오른쪽으로 이동할 수 있다. 또는 (b) 중력의 방향을 뒤집을 수 있다.
중력의 방향을 바꾸면, 선장의 '아래'에 있는 칸이 행 번호가 1 큰 칸과 행 번호가 1 작은 칸 사이에서 뒤바뀐다 (첫 번째 행의 번호는 1, 마지막 행의 번호는 N이다). 처음에는 행 번호가 1 큰 칸이 선장의 아래에 있다.
보비디언 선장이 최소 횟수의 중력 뒤집기로 비팔로 박사에게 도달하도록 도와주자. 불가능하면 -1을 출력한다.
첫째 줄: 공백으로 구분된 두 정수 N과 M.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄은 i번째 행을 설명한다. '.'는 빈 칸, '#'는 막힌 칸, 'C'는 보비디언 선장의 시작 위치, 'D'는 비팔로 박사의 시작 위치를 나타낸다.
보비디언 선장이 비팔로 박사에게 도달하기 위해 중력을 뒤집어야 하는 최소 횟수를 나타내는 정수 하나, 불가능하면 -1.
gravity.in · 출력을 쓸 파일 gravity.out5 5
#####
#...#
#...D
#C...
##.##3Output details: The captain flips gravity and falls up to row 2, moves right twice, flips again to fall to row 4, moves right once, then flips again to fall to Doctor Beefalo. Three flips total.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > US Open > Silver