전설의 경단 메이커 4
시간 제한1초메모리 제한512 MB
P, W, G로 이루어진 R×C 격자에서 P-W-G 또는 G-W-P 순서로 읽히는 겹치지 않는 세 칸 줄을 최대한 많이 고르는 문제입니다.
문제
당신은 경단(당고)을 만드는 전문가입니다. 지금 경단을 꼬치에 꽂고 있습니다.
경단은 R행 C열의 직사각형 격자에 놓여 있으며, 각 칸에는 경단이 정확히 하나씩 있습니다. 경단의 색은 분홍(P), 흰색(W), 초록(G) 중 하나입니다. 세로 방향(위에서 아래), 가로 방향(왼쪽에서 오른쪽), 대각선 방향(왼쪽 위에서 오른쪽 아래, 또는 오른쪽 위에서 왼쪽 아래) 중 하나로 연속된 세 칸을 고릅니다. 그다음 이 칸들의 경단을 한쪽 끝에서 다른 쪽 끝으로 차례로 가져와 순서대로 꼬치에 꽂으면 '경단 꼬치'가 됩니다. 예를 들어 세로로 연속된 세 칸을 골랐다면 위, 가운데, 아래 순서 또는 아래, 가운데, 위 순서로 경단을 가져올 수 있습니다. 가운데, 아래, 위 순서나 아래, 위, 가운데 순서로는 가져올 수 없습니다. 한 경단을 두 개 이상의 꼬치에 꽂을 수는 없습니다.
경단 꼬치는 색이 순서대로 분홍-흰색-초록 또는 초록-흰색-분홍일 때 '아름답다'고 합니다.
아름다운 경단 꼬치를 최대 몇 개 만들 수 있습니까?
입력
입력은 다음 형식으로 주어집니다.
R C
D1
.
.
.
DR
Di (1 이상 R 이하)는 P, W, G로 이루어진 길이 C의 문자열입니다. Di의 j번째 문자는 위에서 i번째 행, 왼쪽에서 j번째 열에 있는 경단의 색입니다.
출력
R줄을 출력합니다. 각 줄은 C개의 문자로 이루어집니다. i번째 줄의 j번째 문자는 다음 중 하나입니다.
- 해당 칸과 바로 위, 바로 아래 칸의 경단으로 아름다운 꼬치를 만들 수 있으면
|. - 해당 칸과 바로 왼쪽, 바로 오른쪽 칸의 경단으로 아름다운 꼬치를 만들 수 있으면
-. - 해당 칸과 왼쪽 위, 오른쪽 아래 칸의 경단으로 아름다운 꼬치를 만들 수 있으면
\\. - 해당 칸과 오른쪽 위, 왼쪽 아래 칸의 경단으로 아름다운 꼬치를 만들 수 있으면
/. - 그 밖의 경우에는 입력에서 해당 칸 경단의 색인
P,W,G.
제한
- 3 ≤ R ≤ 500
- 3 ≤ C ≤ 500
- Di (1 이상 R 이하)는 P, W, G로 이루어진 길이 C의 문자열입니다.