아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

814 - 2

시간 제한0.814초메모리 제한814 MB

요약
8 곱하기 14 격자에 숫자를 채워, 1부터 X까지의 모든 수를 인접한 칸을 따라 읽을 수 있게 할 때 X를 최대화하는 문제입니다.
난이도

어려움10점 중 9점

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

문제

숫자 0~9로만 이루어진 8 × 14 크기의 표를 만들어 출력해보자. 다음과 같은 방식으로 만들어진 수를 표에서 "읽을 수 있다"라고 한다:

표 위의 어떤 칸에서 시작하여, 상하좌우 혹은 대각선으로 인접한 칸으로 이동하면서 칸에 적힌 숫자를 순서대로 이어붙여 수를 만든다.

지나갔던 칸을 다시 방문하여 수를 이어 붙이는 것은 가능하지만, 칸을 건너뛰거나, 같은 칸에 계속 머물러서 수를 이어 붙이는 것은 안 된다.

아래와 같은 2 × 3 크기의 표를 예로 들어보자.

원으로 표시된 1에서 시작해서, 아래쪽, 오른쪽, 왼쪽위, 왼쪽으로 이동하면 12314가 만들어지므로, 이 표에서는 12,314를 읽을 수 있다. 만약, 4에서 시작해서 역순으로 이동하면 41,321도 읽을 수 있을 것이다.

그러나, 4에서 시작해서 칸을 건너뛰어 이동하는 것은 불가능하므로 46은 읽을 수 없으며, 1에서 시작해서 같은 칸에 계속 머물러 있을 수 없어서 11또한 읽을 수 없다.

입력

입력은 주어지지 않는다.

출력

숫자 0 ~ 9 로만 이루어진 8 × 14 크기의 표를 출력하면 된다.

출력된 표에서 1부터 X까지의 수를 모두 읽을 수 있는데, X+1은 읽을 수 없다면 X점을 받게 된다.

예제1

  1. 예제 1

    입력
    예상 출력
    10203344536473
    01020102010201
    00000000008390
    00000000000400
    00000000000000
    55600000000089
    78900066000089
    00000789000077