연결 (Connect)

80x25 텍스트 터미널에서 주로 돌아가던, 세 글자짜리 16비트 운영체제가 PC 시장을 지배하던 시절, "Nibbles"는 모두가 가장 좋아하던 컴퓨터 게임이었습니다. 하지만 이 문제는 Nibbles에 관한 것이 아니라, Nibbles와 거의 비슷하면서도 사실은 전혀 다른 "Connect"라는 게임에 관한 것입니다.

Connect는 R개의 행과 C개의 열로 이루어진 정사각형 칸들의 판 위에서 진행되며, R과 C는 모두 홀수입니다. 행은 1부터 R까지, 열은 1부터 C까지 번호가 매겨집니다. 각 칸은 비어 있거나 벽으로 막혀 있습니다. 또한 모든 판은 다음 규칙을 만족합니다.

• 두 좌표가 모두 짝수인 칸은 방(room)입니다. 방은 절대 막히지 않습니다.
• 두 좌표가 모두 홀수인 칸은 장벽(barrier)입니다. 장벽은 항상 막혀 있습니다.
• 그 밖의 모든 칸은 통로(corridor)입니다. 통로는 막혀 있을 수도, 뚫려 있을 수도 있습니다.
• 판의 바깥 테두리에 있는 통로는 항상 막혀 있습니다.

장벽은 + 문자로, 막힌 수평 통로는 | 문자로, 막힌 수직 통로는 - 문자로 표시합니다. 방과 뚫린 통로는 공백 문자로 표시합니다.

게임이 시작될 때, 짝수 개의 말(대문자 X로 표시)이 각각 서로 다른 방 하나씩에 놓입니다. 말 A와 B 사이의 경로란, A에서 시작하여 B에서 끝나고 매 단계마다 상하좌우 네 방향 중 하나로 한 칸씩 이동하는, 비어 있는 칸들의 나열입니다(경로에는 양 끝 칸 A와 B도 포함됩니다). 경로의 길이는 A에서 B까지 가는 데 필요한 이동 횟수이며, 이는 경로에 포함된 칸의 수에서 1을 뺀 값과 같습니다.

플레이어는 먼저 모든 말을 짝으로 나눈 뒤, 각 짝의 두 말을 경로로 연결해야 하며, 이때 어떤 두 경로도 같은 칸을 공유해서는 안 됩니다. 완성된 게임의 점수는 모든 경로 길이의 합입니다.

+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+|             |            |  .......    | + + + + + + + +            + +.+ + +.+ + + |X  |   |     |            |X..|   |.    | + + + + + + + +            + + + + +.+ + + |   |   |  X  |            |   |   |..X  | +-+ + + + + + +            +-+ + + + + + + |       |     |            |       |     |+ + + +-+-+-+-+            + + + +-+-+-+-+ |            X|            |            X|+ + +-+-+-+-+ +            + + +-+-+-+-+.+ |             |            |  ...........| + + + + + + + +            + +.+ + + + + + |  X|         |            | X|          | + + + + + + + +            + + + + + + + + |   |         |            |   |         |+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+

시작 배치가 주어질 때, 모든 말을 짝지어 서로 칸을 공유하지 않는 경로들로 연결했을 때 얻을 수 있는 가장 작은 점수를 구하세요. 모든 말을 연결하는 방법이 적어도 하나는 항상 존재함이 입력 데이터로 보장됩니다.

첫 번째 줄에는 두 홀수 정수 R과 C가 주어집니다 (5 <= R <= 25, 5 <= C < 80). 각각 행과 열의 수입니다.

이어지는 R개의 줄에는 판의 한 행을 나타내는 C개의 문자가 주어집니다. 각 문자는 +, |, - 중 하나(장벽 또는 막힌 통로), 공백 문자(뚫린 통로 또는 방), 또는 X(방 안에 놓인 말) 입니다.

판 위에는 적어도 두 개의 말이 있으며, 말의 개수는 항상 짝수입니다.

정수 하나를 출력합니다. 모든 말을 짝으로 나누고 각 짝을 서로 칸을 공유하지 않는 경로로 연결하는 모든 방법 중에서, 경로 길이 합의 최솟값(즉 가능한 가장 작은 점수)입니다.