전설의 경단 메이커 5
시간 제한1초메모리 제한512 MB
격자의 각 칸은 P, W, G 색 경단입니다. 가로, 세로, 대각선으로 연속한 세 칸을 P-W-G 또는 G-W-P 순서로 겹치지 않게 최대한 많이 고르고, 사용된 칸을 방향 기호로 표시합니다.
문제
당신은 맛있는 경단을 만드는 전문 장인이다. 이제 경단을 막대에 꽂을 차례이다.
경단은 행 열의 직사각형 격자에 놓여 있으며, 각 칸에는 경단이 하나씩 있다. 경단의 색은 분홍(P), 흰색(W), 초록(G) 중 하나이다. 세로 방향(위에서 아래), 가로 방향(왼쪽에서 오른쪽), 대각선 방향(왼쪽 위에서 오른쪽 아래, 또는 오른쪽 위에서 왼쪽 아래) 중 하나를 골라 연속한 경단 세 개를 선택한다. 그다음 선택한 세 칸에서 경단을 하나씩 끝에서 끝으로 가져와 순서대로 막대에 꽂으면 경단 막대가 된다. 예를 들어 세로로 연속한 세 칸을 고르면 위, 가운데, 아래 순서 또는 아래, 가운데, 위 순서로 경단을 가져와 꽂을 수 있다. 가운데, 아래, 위 순서나 아래, 위, 가운데 순서로는 가져올 수 없다. 또한 한 경단을 두 개 이상의 막대에 꽂을 수 없다.
막대의 경단 색이 순서대로 분홍, 흰색, 초록이거나 초록, 흰색, 분홍이면 그 막대를 아름다운 막대라고 한다. 아름다운 막대를 최대한 많이 만들려고 한다.
아름다운 막대를 몇 개 만들 수 있는가?
입력
첫 줄에 과 가 주어진다. 이어지는 개의 줄에는 각각 길이 의 문자열 가 주어진다. 의 번째 문자는 위에서 번째, 왼쪽에서 번째 칸에 있는 경단의 색이다. 각 문자는 P, W, G 중 하나이다.
R C
D1
.
.
.
DR
출력
개의 줄을 출력한다. 각 줄은 길이 의 문자열이다. 번째 줄의 번째 문자는 행 열 칸을 나타낸다.
- 그 칸의 경단을 바로 위 칸, 바로 아래 칸과 함께 아름다운 막대에 쓰면
|를 출력한다. - 바로 왼쪽 칸, 바로 오른쪽 칸과 함께 쓰면
-를 출력한다. - 왼쪽 위 대각선 칸, 오른쪽 아래 대각선 칸과 함께 쓰면
\를 출력한다. - 오른쪽 위 대각선 칸, 왼쪽 아래 대각선 칸과 함께 쓰면
/를 출력한다. - 그 밖의 경우에는 입력에 있던 P, W, G 중 원래 색 문자를 출력한다.
S1
.
.
.
SR
제한
- .
- .
- 각 는 P, W, G로 이루어진 길이 의 문자열이다.