34511번 - Polyominonal Puzzle

문제

재호는 퍼즐을 맞추는 데에 있어 뛰어난 감각이 있다. 12ドル$개의 조각으로 푸는 펜토미노 퍼즐을 마스터하고 지루함을 느낀 재호는 새로운 방법으로 퍼즐을 즐기고자 했다. 미노 퍼즐 조각을 서로 맞닿아있는 선분들의 길이를 구하면서 퍼즐을 풀고자 한다. 여러분은 재호를 도울 프로그램을 작성해야 한다.

크기가 $N \times M$인 격자 모양의 보드 위에는 두 개의 퍼즐 조각이 놓여 있다.

• 하나는 $X$ 퍼즐 조각이고, 다른 하나는 $Y$ 퍼즐 조각이다.
• 각 퍼즐 조각은 서로 다른 1ドル \times 1$ 크기의 칸들을 변끼리 이어 붙여 만든 연결된 도형이다.
• 보드에 놓인 두 퍼즐 조각은 서로 겹치지 않고 한 개씩 존재한다.

두 퍼즐 조각이 서로 맞닿아있는 선분들의 길이의 총합을 구해보자.

입력

첫 번째 줄에 보드의 세로 크기 $N$과 가로 크기 $M$이 공백으로 구분되어 주어진다.

이후 $N$개의 줄에 걸쳐 격자의 상태가 주어진다. 그중 $i$번째 줄에는 $i$번 행의 상태를 나타내는, 길이가 $M$인 문자열 $S_i$가 주어진다. 문자열 $S_i$는 다음 세 가지 문자로 구성된다. $(1 \le i \le N)$

• X: $X$ 퍼즐 조각에 속하는 칸
• Y: $Y$ 퍼즐 조각에 속하는 칸
• .: 빈칸

입력으로 주어지는 퍼즐 조각은 각각 연결되어 있으며, 서로 겹치지 않는다.

출력

첫 번째 줄에 두 퍼즐 조각이 서로 맞닿아있는 선분들의 길이의 총합을 출력한다.

제한

• 2ドル \leq N, M \leq 100$

힌트