로봇 청소기

직사각형 모양의 방을 로봇 청소기로 청소하려고 한다. 로봇 청소기가 지나갈 경로는 사용자가 직접 정할 수 있다.

방은 $1 \times 1$ 크기의 정사각형 칸으로 나뉘어 있고, 로봇 청소기의 크기도 $1 \times 1$이다. 각 칸은 깨끗한 칸이거나 더러운 칸이며, 로봇 청소기가 더러운 칸을 지나가면 그 칸은 깨끗해진다.

일부 칸에는 $1 \times 1$ 크기의 가구가 놓여 있으며, 로봇 청소기는 가구가 있는 칸으로는 이동할 수 없다.

로봇 청소기는 한 번 이동할 때 상하좌우로 인접한 칸으로 갈 수 있고, 같은 칸을 여러 번 지나가도 된다.

방의 정보가 주어질 때, 모든 더러운 칸을 깨끗하게 만드는 데 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 $w$와 세로 크기 $h$가 주어진다. ($1 \le w, h \le 20$) 둘째 줄부터 $h$개의 줄에 걸쳐 방의 정보가 주어지며, 각 줄은 $w$개의 문자로 이루어진다. 사용되는 문자는 다음 네 가지뿐이다.

더러운 칸의 개수는 최대 $10$개이며, 로봇 청소기는 항상 정확히 하나 존재한다.

입력의 마지막 줄에는 $0$이 두 개 공백으로 구분되어 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 모든 더러운 칸을 깨끗하게 만드는 최소 이동 횟수를 한 줄에 하나씩 출력한다. 방문할 수 없는 더러운 칸이 하나라도 있으면 $-1$을 출력한다.