로렐 크리크

로렐 크리크는 캠퍼스를 둘로 가르는 위험한 강으로, 거위와 비버 같은 위험한 생물이 사는 곳이다. 당신이 할 일은 물에 젖지 않고 이 강을 건너는 방법을 찾는 것이다.

강을 건너기 위해 강 가운데에 있는 여러 나무 그루터기를 이용한다. 그루터기는 다음 행동을 고민하는 동안 안전하게 서 있을 수 있는 곳이며, 한 그루터기에서 다른 그루터기로는 두 그루터기를 잇는 통나무 위를 걸어서 이동한다.

가고 싶은 그루터기에 연결된 통나무가 없어도 방법이 없는 것은 아니다. 지금 서 있는 그루터기에 인접한 통나무를 집어 들어, 원하는 그루터기에 닿도록 다른 곳에 내려놓을 수 있다. 통나무가 그루터기에 인접하다고 인정되려면 방향이 알맞아야 한다. 예를 들어 S-S의 통나무는 두 그루터기에 모두 인접하지만, S|S의 통나무는 어느 그루터기에도 인접하지 않는다.

모든 그루터기는 정사각형 격자의 한 점에 있다. 두 그루터기가 건너기의 시작점과 끝점으로 지정되어 있다. 같은 행 또는 같은 열에 있는 두 그루터기는 통나무로 이을 수 있다. 매 순간 당신은 다음 중 정확히 한 가지 행동을 할 수 있다.

• 지금 서 있는 그루터기에 인접한 통나무를 건너, 그 통나무의 반대쪽 끝에 있는 그루터기로 이동한다.
• 지금 서 있는 그루터기에 인접한 통나무를 집어 든다. 한 번에 두 개 이상의 통나무를 들 수는 없다.
• 들고 있는 통나무를 내려놓아 지금 서 있는 그루터기와 다른 그루터기를 잇는다. 통나무의 길이는 그 그루터기에 닿기에 정확히 알맞아야 한다. 통나무는 물 위에 놓여야 한다. 즉, 두 그루터기 사이에 다른 그루터기가 곧바로 놓여 있거나, 이미 물 위에 놓인 다른 통나무와 교차하게 된다면 두 그루터기를 이을 수 없다.

첫째 줄에는 테스트 케이스의 수를 나타내는 정수 하나가 주어진다. 각 테스트 케이스의 첫째 줄에는 격자의 행 수와 열 수를 나타내는 두 정수 $r$와 $c$가 주어지며, $1 \le r \le 15$, $1 \le c \le 15$이다. 이어지는 $r$개의 줄에는 각각 $c$개의 문자가 주어지며, 그 의미는 다음과 같다. S는 그루터기, B와 E는 각각 건너기의 시작 그루터기와 끝 그루터기를 나타낸다. - 또는 |가 연속으로 이어진 부분은 하나의 통나무이며, 그 길이는 기호의 개수에 비례한다. .는 물만 있는 빈 격자점을 나타낸다. 강에 있는 그루터기는 15개를 넘지 않는다.

각 테스트 케이스마다, 처음 상태에서 끝 그루터기에 도달하는 데 필요한 최소 행동 횟수를 정수 하나로 한 줄에 출력한다. 여기서 한 번의 행동이란 위의 세 가지 합법적 행동(건너기, 집어 들기, 내려놓기) 중 하나를 말한다. 끝 그루터기에 도달할 수 없으면 0을 출력한다.