시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 (하단 참고) | 512 MB | 70 | 33 | 14 | 51.852% |
Albert는 크기가 n × n 인 2차원 행렬 모양의 게임 보드를 이용한 "소용돌이" 게임을 즐긴다. 편의상 게임 보드의 r행 c열에 해당하는 칸을 (r, c)로 나타내도록 한다.
이 게임 보드의 각 칸에는 영문 대문자 알파벳이 ('A'-'Z') 하나씩 적혀있다. 예를 들어, 아래 그림의 좌측은 크기가 3 x 3인 게임 보드를 나타낸다. (1, 2) 칸에는 "C"가 적혀있고 (3, 1) 칸에는 "G"가 적혀있다.
그림의 우측은 크기가 5 x 5인 게임 보드를 나타낸다. 이 게임 보드의 가장 바깥쪽 칸에는 "A" 혹은 "B"가 적혀있다 (총 16개의 칸이 이에 해당한다). 가장 안쪽에 위치한 칸에는 "Z"가 적혀있다. 나머지 칸에는 "X" 혹은 "Y"가 적혀있다 (총 8개의 칸이 이에 해당한다).
구체적으로, n x n인 게임 보드의 "가장 바깥쪽"칸 부터 "가장 안쪽"칸은 아래와 같이 정의한다.
소용돌이 게임은 아래와 같은 규칙에 따라 한 칸씩 선택하여 총 n2개의 칸을 선택하는 게임이다.
위 규칙을 지키면서 모든 n2개의 칸을 선택하여 얻을 수 있는 (길이가 n2인) 문자열을 "소용돌이 문자열" 이라 부른다.
예를 들어 위의 3 x 3 게임 보드의 경우 아래와 같은 방법으로 소용돌이 문자열을 얻을 수 있다:
같은 게임 보드에서 (3, 3)에서 시작하는 경우 위와 다른 소용돌이 문자열을 얻을 수 있다:
이 외에도 (1, 3) 혹은 (3, 1)에서 시작할 수 있다.
Albert는 임의의 게임 보드를 이용해서 얻을 수 있는 "최대" 소용돌이 문자열과 "최소" 소용돌이 문자열이 무엇인지 궁금하다.
위의 예제의 경우 최대 소용돌이 문자열은 "IHGEBCDFA" 이며 최소 소용돌이 문자열은 "BCDFIHGEA" 이다.
최대 (최소) 소용돌이 문자열은 소용돌이 게임에서 얻을 수 있는 모든 소용돌이 문자열 중 사전순으로 가장 늦게 (먼저) 나오는 문자열이다.
입력 첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄에 게임 보드의 크기 n이 주어진다.
다음 n줄에 걸쳐 각 줄에 길이 n인 문자열이 주어진다.
각 테스트 케이스의 정답인 최대 소용돌이 문자열과 최소 소용돌이 문자열을 공백으로 구분하여 각 줄에 출력한다.
6 3 BCD EAF GHI 2 AB XY 2 GA GD 4 ABCD BHAE CHIF DEFG 5 LGELG LGLGE GGLGE LGEGL LGLGL 5 ABABA BXYXB AYZYA BXYXB ABABA
IHGEBCDFA BCDFIHGEA YXAB ABYX GGDA ADGG GFEDCBABCDEFIHHA ABCDEFGFEDCBHAIH LLGLLGLGLLEEGLEGGLGGGEGGL GEELLGLGLLGLLGELGGGEGGGLL ABABABABABABABABXYXYXYXYZ ABABABABABABABABXYXYXYXYZ
예제 1: 본문에서 다루었다.
예제 2-5: 추가 설명 없음
예제 6: 본문에서 다룬 예제이다. 이 게임 보드의 경우 모든 소용돌이 문자열이 같다.