시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 3 2 2 100.000%

문제

새 학기 고교 반장선거를 할 때가 되었다. 선거에는 P양과 L군이 출마한다. 반장은 교사와 매우 밀접한 관계를 가지는 자리이기 때문에, 여고생이 좋아서 교사가 된 당신은 반드시 P양이 당선되도록 하고 싶다.

총 16명인 학생들의 자리 배치는 4*4의 정사각 격자 형태이다. 당신은 각각의 학생들이 누구에게 표를 던질 것인지를 미리 알고 있다. 당신은 7명을 반의 대표로 삼아 그들에게만 투표권을 주는 방법으로 선거를 조작하고자 한다. 4명 이상의 PP에게 투표할 경우 P가 당선되고, 그렇지 않을 경우에는 L이 당선된다.

당신은 투표권을 줄 7명의 학생을 결정하였는데, 선거가 자연스러워 보이게 하기 위해서 이 학생들을 떨어뜨려 놓으려고 한다. 해당 학생들만 자리를 바꿀 경우에 부정 선거로 보일 위험이 있으므로, 학생들의 자리 배정을 새롭게 하려 한다. 또한 학생들의 자리를 바꿀 때, 서로 붙어 있는 두 학생의 자리만 바꾸려고 한다. 한 번 자리를 바꾼 학생이라 하더라도, 얼마든지 자리를 더 바꿀 수도 있다.

당신은 각 학생이 어느 후보에게 지지할지에만 관심이 있기 때문에, 같은 후보를 지지할 경우에 같은 학생으로 간주한다.

당신은 의혹을 최소화하기 위해서 자리바꿈을 최소화 하려 한다.

입력

'P' 또는 'L‘을 값으로 갖는 4*4 행렬이 공백 없이 주어진다. 값은 그 위치의 학생이 누구에게 투표할 것인지를 나타낸다. 이는 현재의 배치를 나타낸다. 다음 줄에는 빈 줄이 0개 이상 들어오고, 최종적으로 만들 학생들의 자리 배치가 같은 방식으로 주어진다.

출력

최소의 자리바꿈 횟수를 출력한다.

예제 입력

LLLL
PPPP
LLLP
PPLP

LPLP
PLPL
LPLP
PLPL

예제 출력

4

힌트