만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

전설의 경단 메이커 3

시간 제한1초메모리 제한512 MB

요약
P, W, G로 이루어진 격자에서 연속한 세 칸을 겹치지 않게 골라 P-W-G 또는 G-W-P 순서가 되는 막대를 최대한 많이 만드는 문제입니다.
난이도

보통10점 중 5점

유형
행렬, 그리디, 구현
정답자
아직 제출이 없습니다

문제

당신은 경단을 만드는 전문 장인이다. 맛있는 경단을 막대에 꽂고 있다.

경단은 R행 C열의 직사각형 격자에 놓여 있고, 각 칸에는 경단이 하나씩 있다. 경단의 색은 분홍(P), 흰색(W), 초록(G) 중 하나다. 세로, 가로, 대각선(왼쪽 위에서 오른쪽 아래, 또는 오른쪽 위에서 왼쪽 아래) 방향 중 하나를 골라 연속한 세 칸을 선택할 수 있다. 그다음 선택한 칸에서 경단을 한쪽 끝에서 반대쪽 끝까지 순서대로 집어 막대에 꽂으면 경단 꼬치가 된다. 예를 들어 세로로 세 칸을 고르면 위, 가운데, 아래 순서나 아래, 가운데, 위 순서로 경단을 집을 수 있다. 가운데, 아래, 위 순서나 아래, 위, 가운데 순서로는 집을 수 없다. 한 경단을 두 개 이상의 꼬치에 꽂을 수는 없다.

꼬치의 색이 순서대로 P, W, G이거나 G, W, P이면 아름다운 꼬치다. 아름다운 꼬치를 최대한 많이 만들고자 한다.

아름다운 꼬치를 몇 개 만들 수 있는가?

입력

첫 줄에 R과 C가 주어진다. 이어지는 R개의 줄에는 P, W, G로만 이루어진 길이 C의 문자열 Di가 주어진다. Di의 j번째 문자는 i행 j열 칸에 있는 경단의 색이다.

출력

R개의 줄을 출력한다. 각 줄 Si는 P, W, G, |, -, , /로 이루어진 길이 C의 문자열이다. Si의 j번째 문자는 i행 j열 칸을 나타낸다.

  • |는 이 칸, 바로 위 칸, 바로 아래 칸으로 아름다운 꼬치를 만든다는 뜻이다.
  • -는 이 칸, 바로 왼쪽 칸, 바로 오른쪽 칸으로 아름다운 꼬치를 만든다는 뜻이다.
  • \는 이 칸, 왼쪽 위 칸, 오른쪽 아래 칸으로 아름다운 꼬치를 만든다는 뜻이다.
  • /는 이 칸, 오른쪽 위 칸, 왼쪽 아래 칸으로 아름다운 꼬치를 만든다는 뜻이다.
  • 그 밖의 경우에는 이 칸 경단의 색인 P, W, G 중 하나를 출력한다.

제한

3≤R≤5003 \le R \le 500.

3≤C≤5003 \le C \le 500.

Di는 P, W, G로만 이루어진 길이 C의 문자열이다.

예제2

  1. 예제 1

    입력
    3 4
    PWGP
    WGPW
    GWPG
    
    예상 출력
    P-GP
    WGP|
    G-PG
    
  2. 예제 2

    입력
    3 4
    PWWP
    WWWW
    PGGP
    
    예상 출력
    PWWP
    W\/W
    PGGP