이미지 둘레

병리학 실험실의 기사들은 디지털로 변환된 슬라이드 이미지를 분석한다. 슬라이드 위의 물체는 마우스로 클릭하여 분석 대상으로 선택한다. 물체를 측정하는 유용한 값 중 하나는 그 경계선의 둘레 길이이다. 이 문제의 목표는 선택된 물체의 둘레를 구하는 것이다.

디지털 슬라이드는 문자로 이루어진 직사각형 격자로 주어진다. 마침표 .는 빈 공간을, 대문자 X는 물체의 일부를 나타낸다. 간단한 예는 다음과 같다.

XX     격자 1        .XXX   격자 2
XX                   .XXX
                     .XXX
                     ...X
                     ..X.
                     X...

격자 칸의 X는 경계를 포함한 그 칸 전체가 어떤 물체에 속함을 뜻한다. 두 X는 격자 칸이 변 또는 꼭짓점에서 맞닿을 때 인접한다고 한다. 즉 하나의 X는 자신을 둘러싼 8개 칸의 X와 모두 인접한다.

XXX
XXX     가운데 X는 주변 8개의 X와 모두 인접한다
XXX

물체란 인접한 X들의 연결을 따라 서로 이어질 수 있는 모든 X 칸의 집합이다. 격자 1에서는 모든 X가 하나의 물체를 이룬다. 격자 2에는 물체가 두 개 있다. 하나는 왼쪽 아래 칸 하나로만 이루어지고, 나머지 X들이 다른 하나의 물체를 이룬다.

기사는 항상 X 위를 클릭하며, 그 칸이 속한 물체가 선택된다. 행과 열은 왼쪽 위 모서리에서 시작해 1부터 번호를 매기며, 클릭 위치는 (행, 열) 쌍으로 주어진다. 격자 1의 물체는 2행 2열을 클릭하여 선택할 수 있다. 격자 2의 더 큰 물체는 2행 3열을 클릭하면 선택되지만, 4행 3열을 클릭하면 선택되지 않는다.

둘레는 물체 경계선의 길이이다. 각 X를 한 변의 길이가 1인 정사각형으로 본다. 따라서 격자 1의 물체의 둘레는 $8$이다(네 변에 각각 2씩). 격자 2의 더 큰 물체의 둘레는 $18$이며, 위 그림에 나타나 있다.

물체는 완전히 둘러싸인 구멍을 가지지 않는다. 그러므로 아래 왼쪽의 모양들은 나타날 수 없고, 오른쪽의 변형들은 나타날 수 있다.

불가능            가능

XXXX         XXXX   XXXX   XXXX
X..X         XXXX   X...   X...
XX.X         XXXX   XX.X   XX.X
XXXX         XXXX   XXXX   XX.X

.....        .....  .....  .....
..X..        ..X..  ..X..  ..X..
.X.X.        .XXX.  .X...  .....
..X..        ..X..  ..X..  ..X..
.....        .....  .....  .....

입력에는 하나 이상의 격자가 주어진다. 각 격자 앞에는 네 정수가 담긴 줄이 하나 있으며, 순서대로 격자의 행 수, 열 수, 마우스 클릭의 행, 마우스 클릭의 열이다. 네 수는 모두 1 이상 20 이하이다. 그다음 줄부터 격자의 각 행이 한 줄씩 이어지며, 각 행은 .와 X 문자로 이루어진다.

입력의 끝은 네 개의 0이 담긴 줄로 표시된다. 머릿줄의 수들은 공백으로 구분되고, 격자의 행에는 공백이 없다.

각 격자마다 선택된 물체의 둘레를 한 줄에 하나씩 출력한다.