핵융합

세계 최초의 상온 핵융합로가 오늘 완공되어 가동 승인까지 받았다. 그런데 처음 가동했을 때 아무 일도 일어나지 않았다.

당황한 물리학자들이 계산을 몇 번이나 다시 확인한 끝에, 기술자 세 명이 원인을 찾아냈다. 반응로 안의 원자 두 개가 α 고착 상태에 빠진 것이다.

반응로는 $R$행 $C$열의 격자로 생각할 수 있다. 각 칸은 비어 있거나, 중수소 원자 하나를 담고 있거나(그중 두 개가 α 고착 원자다), 폭주 반응을 막는 제어봉으로 막혀 있다. 각 칸은 위, 아래, 왼쪽, 오른쪽으로 맞닿은 네 칸과 인접하고, 가장자리 칸은 인접한 칸이 네 개보다 적다.

반응로에 원자 두 개를 지정해 융합 명령을 내릴 수 있다. 두 원자는 서로 인접한 칸에 있거나, 한쪽에서 다른 쪽까지 인접한 빈 칸으로 이어지는 경로가 있을 때만 융합된다. 두 원자가 융합하면 헬륨이 생겨 날아가고, 두 원자가 있던 칸은 빈 칸이 된다.

반응로를 고치려면 α 고착 원자 두 개를 서로 융합시켜야 한다. 여기에 필요한 명령은 최소 몇 개인가?

그림 1: 첫 번째 예제 입력에 해당하는 반응로다. 검은 칸은 제어봉으로 막힌 칸, 파란 원은 중수소 원자, 노란 원은 α 고착 원자 두 개를 나타낸다. 최적인 융합 순서 하나도 함께 나타냈다.

당신과 동료 기술자들은 상온 핵융합의 마지막 장벽을 넘을 수 있을까?

첫째 줄에 반응로의 행 개수 $R$과 열 개수 $C$가 주어진다. ($1 \le R \le 1000$, $1 \le C \le 1000$)

다음 $R$개 줄에 반응로의 상태가 주어진다. 각 줄은 정확히 $C$개의 문자로 이루어진다.

• .은 빈 칸이다.
• #은 제어봉으로 막힌 칸이다.
• O는 중수소 원자가 있는 칸이다.
• A는 α 고착 원자가 있는 칸이다.

입력에 주어지는 A는 정확히 두 개다.

α 고착 원자 두 개를 서로 융합시키는 데 필요한 융합 명령의 최소 개수를 출력한다. 두 원자를 융합시킬 수 없으면 -1을 출력한다.