전설의 경단 메이커 6
시간 제한1초메모리 제한512 MB
P, W, G 칸으로 이루어진 격자에서 서로 겹치지 않는 꼬치를 최대한 많이 만들고, 각 꼬치의 가운데 W 칸을 방향 기호로 표시합니다.
문제
당신은 전문적으로 경단을 만드는 사람이다. 지금부터 경단을 막대에 꿰어 나간다.
경단은 R행 C열의 직사각형 격자에 놓여 있으며, 각 칸에 경단이 하나씩 들어 있다. 경단의 색은 분홍(P), 흰색(W), 초록(G) 중 하나다. 세로 방향, 가로 방향, 또는 대각선 방향(왼쪽 위에서 오른쪽 아래, 또는 오른쪽 위에서 왼쪽 아래)으로 연속한 경단 세 개를 고른다. 그다음 세 경단을 끝에서 끝까지 순서대로 막대에 꿰어 경단 막대를 만든다. 예를 들어 세로로 세 개를 고르면 위, 가운데, 아래 순서 또는 아래, 가운데, 위 순서로 가져갈 수 있다. 가운데, 아래, 위나 아래, 위, 가운데 순서로는 가져갈 수 없다. 경단 하나를 두 개 이상의 막대에 꿸 수는 없다.
경단 막대의 색이 순서대로 분홍-흰색-초록 또는 초록-흰색-분홍이면 아름다운 막대다. 아름다운 경단 막대를 최대 몇 개 만들 수 있는가?
입력
입력은 다음 형식으로 주어진다.
R C
D1
.
.
.
DR
Di (1 <= i <= R)는 P, W, G로 이루어진 길이 C의 문자열이다. Di의 j번째 문자는 위에서 i번째 행, 왼쪽에서 j번째 열에 있는 경단의 색이다.
출력
S1부터 SR까지 R줄을 출력한다. 각 줄은 길이 C의 문자열이다. Si의 j번째 문자는 i행 j열의 칸을 다음과 같이 나타낸다.
|이 칸을 바로 위, 바로 아래 칸과 함께 아름다운 막대의 가운데로 쓰는 경우.-이 칸을 바로 왼쪽, 바로 오른쪽 칸과 함께 아름다운 막대의 가운데로 쓰는 경우.\이 칸을 왼쪽 위, 오른쪽 아래 칸과 함께 아름다운 막대의 가운데로 쓰는 경우./이 칸을 오른쪽 위, 왼쪽 아래 칸과 함께 아름다운 막대의 가운데로 쓰는 경우.- 그 밖의 경우에는 Di의 j번째 문자와 같은 색 문자 P, W, G를 출력한다.
제한
3 <= R <= 500. 3 <= C <= 500. Di (1 <= i <= R)는 P, W, G로 이루어진 길이 C의 문자열이다.