19571번 - 탐색 게임 점수

연우는 웹서핑을 하다 탐색 게임이라는 이름의 퍼즐을 발견했다.

이 게임은 아래와 같은 규칙을 갖고 있다.

• 100x100 크기의 칸으로 이루어진 정사각형 판이 주어진다.
• 각 칸마다 1에서 10000까지의 수를 원하는 방식으로 채워 넣는다. 단, 같은 수를 여러 번 적어서는 안 된다.
• 수를 모두 적고 나면 탐색을 시작한다.
• 탐색은 1이 적힌 칸부터 시작해서 모든 칸을 한 번씩 방문할 때까지 진행된다.
• 현재 방문 중인 칸에서, 상하 일직선 혹은 좌우 일직선으로 아직 방문하지 않은 칸 중 하나를 골라 해당 칸을 방문한다. 이 때, 방문하지 않은 칸 중 가장 작은 수가 적힌 칸으로 이동한다.
• 위 조건에 맞춰 이동할 수 있는 칸이 없다면, 아직 방문하지 않은 모든 칸 중에서 가장 작은 수가 적힌 칸으로 이동한다. 이 때, 플레이어는 점수를 1점 얻는다.
• 탐색이 완료되면(모든 칸을 한 번씩 방문하면) 1점을 얻는다.

연우는 점수를 최대한 많이 획득하고 싶다. 연우를 도와 점수를 가장 많이 받을 수 있는 수 배치를 출력하는 프로그램을 작성해보자.

입력은 주어지지 않는다.

각 줄마다 수를 100개씩 공백으로 구분하여 출력한다. 총 100줄을 출력하여야 하며 1에서 10000까지의 수를 정확히 한 번씩 포함해야 한다.

규칙을 만족하지 않는 출력일 경우 0점을 획득, 그 외의 경우 문제에서 주어진 규칙에 따라 플레이어가 받게 되는 점수만큼을 획득하게 된다.