들판 길찾기
면접 대비시간 제한1초메모리 제한1024 MB
시작 위치 S에서 모자 X까지 걸어갈 때 가져가야 하는 도구의 최소 개수를 구합니다. 낫은 풀, 도끼는 나무 가지, 망치는 바위를 치웁니다.
문제
밭이 어수선해졌고, 방금 가장 아끼는 모자를 목장 한가운데에 두고 왔다는 것을 깨달았다. 모자가 지금보다 더 오래 밖에 있기 전에 가서 가져와야 하지만, 게으르기도 하다. 길에는 장애물이 많다. 긴 풀을 베는 낫, 길을 막는 나무를 쪼개는 도끼, 통과할 수 없는 바위를 부수는 망치가 있지만, 이 도구를 모두 들고 다니고 싶지는 않다. 모자의 위치와 밭 및 모든 장애물의 배치가 주어졌을 때, 모자에 도달하기 위해 가져가야 하는 도구의 최소 개수를 구하라.
입력
첫 줄에 이어지는 데이터 세트의 개수 n이 주어진다. 각 데이터 세트는 정사각형 밭의 한 변의 길이 s로 시작한다. 이어서 s개의 줄에 밭의 지도가 주어진다. '.'은 빈 공간, 'X'는 모자, 'S'는 집을 나서는 시작 위치, 'R'은 바위, 'B'는 나무 가지, 'G'는 긴 풀을 뜻한다. 상하좌우로만 이동할 수 있으며 대각선 이동은 할 수 없다.
출력
각 테스트 케이스마다 모자를 되찾는 데 필요한 도구의 최소 개수를 출력한다.