시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB104029919728.886%

문제

우주의 인구를 반으로 줄이려는 악당 타노진스는 우주의 인구 수를 조절할 수 있는 밸런스 스톤이라는 보석을 차지하려고 한다. 이에 맞서는 씨벤저스 멤버 캡틴 학규는 타노진스보다 먼저 밸런스 스톤을 발견하여 파괴하려고 한다.

밸런스 스톤은 N × N 블록으로 이루어진 숫자 퍼즐을 완성하면 얻을 수 있다. 이 숫자 퍼즐은 1가지 블록의 수가 비어져 있는 상태이며, 규칙을 만족하는 수 M을 블록에 채워넣으면 퍼즐이 완성된다. 규칙은 다음과 같다.

[ 규칙 ]

  1. M을 채워넣었을 때 같은 행에 있는 수의 합은 모두 같아야 한다.
  2. M을 채워넣었을 때 같은 열에 있는 수의 합은 모두 같아야 한다.
  3. M을 채워넣었을 때 블록의 대각선의 있는 수들의 합도 모두 같아야 한다.
  4. 규칙 1, 2, 3의 합은 모두 같아야 한다.
  5. 어떠한 수를 M에 넣어도 규칙 1, 2, 3을 만족하지 못한다면 -1을 블록에 채워 넣으면 블록이 완성된다.

캡틴 학규를 도와 퍼즐을 완성하고 우주의 평화를 지키자

입력

입력의 첫째 줄에 맵의 크기 N(2 ≤ N ≤ 500)이 주어진다. 다음 N줄에 각 블록의 수 k가 N개가 주어진다. (1 ≤ k ≤ 1,000,000,000의 자연수), 비어있는 블록은 수 0으로 주어지며 조건을 만족하는 수 M이 존재할 시 무조건 자연수 값이 되도록 주어진다.

출력

퍼즐의 조건을 만족하는 수 M을 출력한다.

예제 입력 1

3
6 1 8
7 5 3
2 0 4

예제 출력 1

9

예제 입력 2

2
1 0
2 1

예제 출력 2

-1

출처

University > 인하대학교 > 2018 인하대학교 프로그래밍 경진대회(IUPC) I번

  • 문제의 오타를 찾은 사람: doju
  • 빠진 조건을 찾은 사람: jh05013
  • 잘못된 데이터를 찾은 사람: khj94811
  • 문제를 만든 사람: klight1994
  • 데이터를 추가한 사람: se1620236