전설의 경단 메이커 2
시간 제한1초메모리 제한512 MB
격자에서 겹치지 않는 연속된 세 칸을 골라 P-W-G 또는 G-W-P 순서가 되는 꼬치를 만들고, 각 꼬치를 방향 기호로 표시합니다.
문제
당신은 경단을 만드는 전문가다. 지금 경단을 꼬치에 꽂고 있다.
경단은 행 열의 직사각형 격자에 놓여 있으며, 각 칸에는 경단이 하나씩 있다. 경단의 색은 분홍(P), 흰색(W), 초록(G) 중 하나다.
세로 방향(위에서 아래), 가로 방향(왼쪽에서 오른쪽), 대각선 방향(왼쪽 위에서 오른쪽 아래, 또는 오른쪽 위에서 왼쪽 아래)으로 연속한 경단 세 개를 고를 수 있다. 그다음 고른 칸에서 경단을 양 끝부터 차례로 집어 꼬치 하나에 순서대로 꽂으면 경단 꼬치가 된다. 예를 들어 세로로 연속한 세 칸을 골랐다면 위, 가운데, 아래 순서 또는 아래, 가운데, 위 순서로 경단을 집을 수 있다. 가운데, 아래, 위 순서나 아래, 위, 가운데 순서로는 집을 수 없다. 한 경단을 두 개 이상의 꼬치에 꽂을 수는 없다.
경단 꼬치는 색이 분홍, 흰색, 초록 순서이거나 초록, 흰색, 분홍 순서이면 아름답다.
아름다운 경단 꼬치를 최대 몇 개 만들 수 있는가?
입력
입력은 다음 형식으로 주어진다.
R C
D1
.
.
.
DR
()는 P, W, G로만 이루어진 길이 의 문자열이다. 의 번째 문자()는 위에서 번째 행, 왼쪽에서 번째 열에 있는 경단의 색이다.
출력
부터 까지 출력한다. 각 는 P, W, G, |, -, \, /로 이루어진 길이 의 문자열이다. 의 번째 문자는 다음과 같다.
- 해당 칸의 경단, 바로 위 칸, 바로 아래 칸으로 아름다운 꼬치를 만들면
| - 해당 칸의 경단, 바로 왼쪽 칸, 바로 오른쪽 칸으로 아름다운 꼬치를 만들면
- - 해당 칸의 경단, 왼쪽 위 칸, 오른쪽 아래 칸으로 아름다운 꼬치를 만들면
\ - 해당 칸의 경단, 오른쪽 위 칸, 왼쪽 아래 칸으로 아름다운 꼬치를 만들면
/ - 그 밖의 경우에는 해당 칸의 색을 나타내는
P,W,G중 하나이며, 이는 의 번째 문자와 같다.
제한
- 각 는 P, W, G로만 이루어진 길이 의 문자열이다.