시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB56413310725.176%

문제

마알은 체스판 위의 말로, 1-마알, 2-마알, ..., 9-마알이 있다. K-마알은 한 번 이동할 때 나이트의 이동 방식 K번을 연속해서 사용할 수 있다. 체스판 위에 마알이 올라와 있다. 모든 마알이 한 곳에 모으려고 할 때, 최소 이동 횟수를 구해보자.

한 번에 마알 하나만 이동할 수 있고, 이동하는 중, 이동을 마친 후 같은 칸에 여러 개의 마알이 있어도 된다.

입력

첫째 줄에 체스판의 세로 크기 N, 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 첫 행부터 주어지며, 한 행의 정보는 공백없이 주어진다. 체스판의 빈 칸은 '.', 숫자 K는 해당 위치에 K-마알이 놓여 있음을 의미한다. 하나 이상의 마알이 있는 경우만 입력으로 주어진다.

출력

모든 마알을 한 곳에 모으기 위한 이동 횟수의 최솟값을 출력한다. 만약, 모든 마알을 한 곳에 모을 수 없다면, -1을 출력한다.

제한

  • 1 ≤ N, M ≤ 10

예제 입력 1

3 4
...1
....
2...

예제 출력 1

2

예제 입력 2

8 8
........
.1......
........
....3...
........
........
.7......
........

예제 출력 2

2

예제 입력 3

3 2
..
2.
..

예제 출력 3

0

예제 입력 4

1 8
.1....1.

예제 출력 4

-1

예제 입력 5

10 10
9133632343
5286698232
8329333369
5425579782
4465864375
8192124686
3191624314
5198496853
1638163997
6457337215

예제 출력 5

121

출처

  • 문제의 오타를 찾은 사람: mendou12