시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 35 28 16 80.000%

문제

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

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

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

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

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

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

입력

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

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

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

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

출력

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

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

각 칸은 아래와 같이 3 x 5 문자로 나타냅니다. '+' 4개로 꼭짓점을 표현하고 정중앙에는 si,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)} 으로 나뉘었습니다.

예제 입력 1

4
AB.C
....
.C.A
A..C

예제 출력 1

yes
###################
#+---+   +---+   +#
#  A | B | . | C  #
#+   +---+   +---+#
#  .   .   .   . |#
#+   +---+---+   +#
#  . | C   . | A |#
#+   +---+   +---+#
#  A   . | .   C  #
#+   +   +---+---+#
###################

예제 입력 2

4
....
GORI
....
BO.J

예제 출력 2

yes
###################
#+---+   +---+---+#
#  . | . | .   . |#
#+   +   +   +---+#
#  G | O | R | I  #
#+---+   +   +---+#
#| .   . | .   . |#
#+---+   +   +---+#
#  B | O | . | J  #
#+   +---+   +---+#
###################

예제 입력 3

4
AAAA
B...
...A
BBBB

예제 출력 3

yes
###################
#+---+---+---+---+#
#  A   A   A   A |#
#+---+---+   +---+#
#| B   . | . | .  #
#+---+   +   +---+#
#  . | . | .   A |#
#+---+   +---+---+#
#| B   B   B   B  #
#+---+---+---+---+#
###################

예제 입력 4

3
XYY
Y.X
YX.

예제 출력 4

yes
###############
#+---+   +   +#
#  X | Y   Y  #
#+---+   +---+#
#| Y   . | X |#
#+   +---+   +#
#| Y | X   . |#
#+---+   +   +#
###############

예제 입력 5

2
XY
YX

예제 출력 5

no

출처

University > 경북대학교 > 2019 Goricon E번

  • 문제를 만든 사람: exqt