버킷 브리게이드
면접 대비시간 제한2초메모리 제한512 MB
10x10 격자에 헛간, 호수, 바위가 하나씩 있을 때, 소들이 호수에서 헛간까지 이어지는 사슬을 이루도록 채워야 하는 빈 칸의 최소 개수를 구한다.
문제
농장에 불이 났고, 소들이 불을 끄기 위해 서둘러 달려간다.
농장은 다음과 같은 문자 격자로 표현된다.
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
문자 'B'는 막 불이 붙은 헛간을 나타낸다. 'L'은 호수, 'R'은 큰 바위의 위치를 나타낸다.
소들은 호수와 헛간 사이의 경로를 따라 늘어서서 물통을 주고받아 불을 끄는 데 도움을 주는 "버킷 브리게이드"를 만들려고 한다. 두 소가 남, 북, 동, 서 방향으로 바로 인접해 있으면 그 사이로 물통을 옮길 수 있다. 호수 옆의 소도 마찬가지다. 소는 호수에 바로 인접해 있을 때만 호수에서 물통에 물을 담을 수 있다. 마찬가지로, 소는 헛간에 바로 인접해 있을 때만 헛간에 물통의 물을 던질 수 있다.
성공적인 버킷 브리게이드를 만들기 위해 소가 차지해야 하는 '.' 칸의 최소 개수를 구하시오.
소는 큰 바위가 있는 칸에 놓을 수 없으며, 헛간과 호수는 서로 바로 인접하지 않음이 보장된다.
입력
입력은 농장의 배치를 나타내는 10개의 문자로 이루어진 10개의 행으로 주어진다. 헛간, 호수, 바위는 각각 정확히 하나씩 있다.
출력
성공적인 버킷 브리게이드를 만드는 데 필요한 소의 최소 수를 정수 하나로 출력한다.
힌트
다음 예시는 최적의 소 수(7)를 사용하는 한 가지 해를 보여준다.
..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....
..........