문제
농부 존은 자신의 헛간에 불이 날때를 대비하여 소들과 함께 소방훈련을 계획중이다.
존의 헛간과 주변 정보는 아래 그림과 같이 10 * 10 격자로 나타낼 수 있다.
.......... .......... .......... ..B....... .......... .....R.... .......... .......... .....L.... ..........
문자 'B'는 헛간을 'L'은 호수를 'R'은 바위를 나타낸다.
존은 헛간으로부터 호수까지 바위를 피하여 최단 경로를 구하고
각 지점에 소들을 배치하여 물 양동이를 전달하도록 할 계획이다.
[입력 예 설명]
아래 그림과 같이 소들을 배치할 수 있으며 필요한 소들의 최소수는 7이다.
.......... .......... .......... ..B....... ..C....... ..CC.R.... ...CCC.... .....C.... .....L....
..........
입력
10개의 행에 헛간과 주변 정보가 입력된다.
출력
소방 훈련을 위하여 필요한 소들의 최소수를 출력한다.
예제1
입력
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
출력
7
출처
USACO 2019 US Open Bronze