Cracking The Safe

면접 대비

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

요약

9개 버튼은 자기 칸과 같은 행, 같은 열의 숫자를 4로 나눈 나머지로 1씩 올린다. 모든 숫자를 0으로 만드는 최소 버튼 누름 횟수를 구하거나, 불가능하면 -1을 출력한다.

난이도: 보통10점 중 5점
유형: 수학, 완전 탐색, 행렬
정답자: 아직 제출이 없습니다

문제

Your little sister misplaced the code for her toy safe - can you help her?

This particular safe has 9 buttons with digital displays. Each button shows a single digit in the range 0..3. When you push one of the buttons, the number it displays is incremented by 1, circling around from 3 to 0. However, pushing a button will also increment the other digits in the same row and the same column as the button pushed.

The safe opens when the display shows nine zeros.

For instance, if you pushed the top-left, center, center, and middle-right buttons, in this order, the safe's display would change like so:

3 1 2     0 2 3     0 3 3     0 0 3     0 0 0
0 1 1  -> 1 1 1  -> 2 2 2  -> 3 3 3  -> 0 0 0
3 2 3     0 2 3     0 3 3     0 0 3     0 0 0

Write a program to determine if the safe can be opened, and if so, how many button pushes it would take!

입력

The input is a single test case, given as 9 digits $d$ , ( $0 \le d \le 3$ ) on 3 lines, representing the digits that are initially displayed on the safe's buttons. Your program will be run multiple times on different inputs.

출력

Output the number of times buttons need to be pushed to open the safe! (The same button may need to be pushed more than once, and you do not have to output which buttons must be pushed.) If the safe cannot be opened, output -1.

예제2

예제 1
입력
```
3 1 2
0 1 1
3 2 3
```
예상 출력
```
4
```
예제 2
입력
```
0 0 3
2 2 3
2 2 1
```
예상 출력
```
-1
```