17500번 - 국경 스페셜 저지

사방이 바다로 둘러싸인 섬에 여러 동물들이 살고 있는 나라가 있습니다.

이 나라는 N×N 모양의 사각 격자로 나타낼 수 있고 각 칸의 내부에는 최대 하나의 종이 살고 있습니다.

최근 서로 다른 종끼리의 잦은 갈등으로 인하여 서로 다른 종끼리 만니지 않도록 하나의 나라를 여러 개의 나라로 나누고자 다음 조건들을 만족하는 국경을 만들고자 합니다.

• 국경은 왼쪽 상단 꼭짓점에서 시작하여 오른쪽 하단 꼭짓점으로 가는 하나의 경로여야 합니다.
• 국경의 경로는 칸의 내부로 진입할 수 없고 오로지 칸의 선분을 지나는 형태로 만들어야 합니다. 바다에 인접한 선분으로도 이동할 수 있습니다.
• 국경의 경로는 한번 지났던 꼭짓점을 다시 지나지 않아야 합니다.
• 서로 다른 종이 국경을 지나지 않고 만날 수 있어선 안됩니다. 동물들은 바다를 통해 이동할 수 없습니다.
• 같은 종끼리 만나지 못해도 괜찮습니다.
• 나라 안에 아무 종이 없어도 됩니다.

« 4×4 모양의 섬과 조건을 만족하는 국경 이미지 »

위의 조건을 만족하는 국경을 그려주세요.

첫 번째 줄에 칸의 크기를 나타내는 정수 N (2 ≤ N ≤ 4) 이 주어집니다.

다음 N개의 줄에는 칸의 정보를 나타내는 길이가 N인 문자열들이 주어집니다. i번째 문자열의 j번째 문자 s_i,j는 i행 j열의 칸의 정보를 나타냅니다. 해당 칸에 동물이 살지 않는 경우 s_i,j는 '.'로 나타내고, 동물이 있을 경우 종의 종류를 알파벳 대문자로 나타냅니다.

종이 같으면 같은 알파벳이고 다르면 다른 알파벳입니다.

입력은 최소 두 종이 살고 있는 경우만 주어집니다.

만약 조건을 만족하는 국경이 존재하지 않는다면 첫 번째 줄에 "no" 를 출력하고 더 이상 아무것도 출력하지 않아야 합니다.

조건을 만족하는 국경이 존재한다면 첫 번째 줄에 "yes" 를 출력하고 다음 줄부터 왼쪽 상단에서 시작하여 오른쪽 하단으로 가는 경로를 아래의 형식에 따라 다음 2N+3 개 줄에 각각 길이가 4N+3인 문자열로 출력합니다.

각 칸은 아래와 같이 3 x 5 문자로 나타냅니다. '+' 4개로 꼭짓점을 표현하고 정중앙에는 s_i,j 로 칸의 정보를 나타내고 양 옆은 공백으로 비웁니다.

+   +
  .  
+   +

각 칸들을 꼭짓점들을 공유하도록 N x N 모양으로 이어 붙여서 전체 칸을 표현합니다. 아래는 N이 3인 경우 9개 칸을 붙였을 때 모양입니다.

+   +   +   +
  .   .   .  
+   +   +   +
  .   .   .  
+   +   +   +
  .   .   .  
+   +   +   +

경로의 경우 지나간 변은 가로 변은 연속한 '-' 3개로 세로 변은 '|' 로 나타냅니다. 아래의 예는 아래, 아래, 오른쪽, 위, 오른쪽, 오른쪽, 아래, 왼쪽, 아래, 오른쪽 순으로 이동했을 때 경로를 나타냅니다.

+   +   +   +
| .   .   .  
+   +———+———+
| . | .   . |
+———+   +———+
  .   . | .  
+   +   +———+

마지막으로 바다를 나타내는 문자 '#'를 칸들 주변에 배치합니다.

###############
#+   +   +   +#
#| .   .   .  #
#+   +———+———+#
#| . | .   . |# 
#+———+   +———+#
#  .   . | .  #
#+   +   +———+#
###############

위의 경우 섬이 총 3개의 영역 {(1, 1), (1, 2), (1, 3), (2, 1)}, {(2, 2), (2, 3), (3, 1), (3, 2)}, {(3, 3)} 으로 나뉘었습니다.