레이팅 미적용농장에 불이 나서, 소들이 불을 끄러 달려가고 있다!
농장은 다음과 같은 \(10 \times 10\) 문자 격자로 표현된다:
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
문자 'B'는 방금 불이 붙은 헛간을 나타낸다. 문자 'L'은 호수를, 'R'은 커다란 바위의 위치를 나타낸다.
소들은 호수와 헛간 사이의 경로를 따라 자리를 잡고 물 양동이를 경로를 따라 전달하여 불을 끄는 "양동이 릴레이"를 만들고자 한다. 양동이는 두 소가 동서남북으로 바로 인접해 있을 때만 소 사이에서 전달될 수 있다. 호수 옆의 소도 마찬가지이다. 소는 호수에 바로 인접해 있을 때만 호수에서 물 한 양동이를 뜰 수 있다. 마찬가지로, 소는 헛간에 바로 인접해 있을 때만 헛간에 물을 끼얹을 수 있다.
성공적인 양동이 릴레이를 만들기 위해 소가 차지해야 하는 '.' 칸의 최소 개수를 구하시오.
소는 커다란 바위가 있는 칸에는 설 수 없으며, 헛간과 호수는 서로 바로 인접해 있지 않음이 보장된다.
문제 제공: Brian Dean
문제 제공: Brian Dean
입력은 각각 10개의 문자로 이루어진 10개의 행으로, 농장의 배치를 나타낸다.
성공적인 양동이 릴레이를 만드는 데 필요한 소의 최소 마릿수를 나타내는 정수 하나를 출력한다.
buckets.in · 출력을 쓸 파일 buckets.out..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........7In this example, here is one possible solution, which involves the optimal number
of cows (7):
..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....
..........
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > US Open > Bronze