Easy as ABC

시간 제한2초메모리 제한1024 MB

요약
A, B, C로 채워진 3 곱하기 3 격자에서 서로 다른 세 칸을 골라 연속한 칸이 인접하도록 만들 수 있는 길이 3 단어 중 사전순으로 가장 앞선 단어를 찾는다.
난이도

쉬움10점 중 3점

유형
완전 탐색, 구현, 그래프, 문자열
정답자
아직 제출이 없습니다

문제

You are playing a word puzzle. The puzzle starts with a 33 by 33 grid, where each cell contains either the letter A, B, or C.

The goal of this puzzle is to find the lexicographically smallest possible word of length 33. The word can be formed by choosing three different cells where the cell containing the first letter is adjacent to the cell containing the second letter, and the cell containing the second letter is adjacent to the cell containing the third letter.

Two cells are adjacent to each other if they share a border or a corner, as shown in the following illustration. Formally, if (r,c)(r, c) denotes the cell in the rrth row and ccth column, then cell (r,c)(r, c) is adjacent to cell (r,c+1)(r, c + 1), (r−1,c+1)(r - 1, c + 1), (r−1,c)(r - 1, c), (r−1,c−1)(r - 1, c - 1), (r,c−1)(r, c - 1), (r+1,c−1)(r + 1, c - 1), (r+1,c)(r + 1, c), and (r+1,c+1)(r + 1, c + 1).

Determine the lexicographically smallest possible word of length 33 that you can find within the grid.

A string ss of length nn is lexicographically smaller than string tt of the same length if there exists an integer 1≤i≤n1 ≤ i ≤ n such that s_j=t_js\_j = t\_j for all 1≤j<i1 ≤ j < i, and s_i<t_is\_i < t\_i in alphabetical order. The following illustration shows some examples on some grids and their the lexicographically smallest possible word of length 33 that you can find within the grids.

입력

Input consists of three lines, each containing three letters, representing the puzzle grid. Each letter in the grid can only be either A, B, or C.

출력

Output the lexicographically smallest possible word of length 33 that you can find within the grid.

예제5

  1. 예제 1

    입력
    BCB
    CAC
    BCB
    
    예상 출력
    ABC
    
  2. 예제 2

    입력
    BCB
    CCC
    CCA
    
    예상 출력
    ACB
    
  3. 예제 3

    입력
    ACA
    CBC
    ACA
    
    예상 출력
    ABA
    
  4. 예제 4

    입력
    ACA
    CAC
    ACA
    
    예상 출력
    AAA
    
  5. 예제 5

    입력
    CCC
    CBC
    CCC
    
    예상 출력
    BCC