USACO 2019 US Open Contest, Bronze1- Bucket Brigade > 문제은행 : 정보올림피아드&알고리즘




3542 : Bucket Brigade

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
1 회   
시도횟수
1 회   

문제

농부 존은 자신의 헛간에 불이 날때를 대비하여 소들과 함께 소방훈련을 계획중이다.

존의 헛간과 주변 정보는 아래 그림과 같이 10 * 10 격자로 나타낼 수 있다.

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

 

문자 'B'는 헛간을 'L'은 호수를 'R'은 바위를 나타낸다.

존은 헛간으로부터 호수까지 바위를 피하여 최단 경로를 구하고

각 지점에 소들을 배치하여 물 양동이를 전달하도록 할 계획이다.

 

[입력 예 설명]

아래 그림과 같이 소들을 배치할 수 있으며 필요한 소들의 최소수는 7이다.

..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....

.......... 

 

 


입력형식

10개의 행에 헛간과 주변 정보가 입력된다.

출력형식

소방 훈련을 위하여 필요한 소들의 최소수를 출력한다.

입력 예

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

출력 예

7


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP