조각 움직이기

5×5 크기의 보드 위에 조각이 최대 5개 놓여 있다. 조각을 적절히 움직여서 모든 조각이 하나의 연결 요소를 이루도록 만들려고 한다. 즉, 상하좌우로 인접한 조각들을 이었을 때 모든 조각 쌍이 적어도 하나의 경로로 서로 연결되어 있어야 한다.

한 번의 이동으로 조각 하나를 상하좌우로 인접한 칸으로 옮길 수 있다. 한 칸에는 조각이 하나만 놓일 수 있으므로, 이미 다른 조각이 있는 칸으로는 옮길 수 없다. 보드의 상태가 주어질 때, 모든 조각이 하나의 연결 요소를 이루기 위해 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오.

첫째 줄부터 다섯째 줄까지 보드의 상태가 주어진다. 빈 칸은 ., 조각은 *로 표시한다. 조각의 개수는 1개 이상 5개 이하이다.

모든 조각이 하나의 연결 요소를 이루기 위한 최소 이동 횟수를 첫째 줄에 출력한다.