마알 모으기
면접 대비시간 제한2초메모리 제한128 MB
체스판 위에서 한 번에 최대 K번 나이트 이동을 할 수 있는 K-말들을 한 칸에 모으는 데 필요한 최소 이동 횟수를 구합니다.
문제
마알은 체스판 위에서 움직이는 말이다. 체스판에는 1-마알, 2-마알, ..., 9-마알이 놓일 수 있다.
K-마알은 한 번의 이동에서 나이트의 이동을 최대 K번 연속으로 할 수 있다. 체스판 위의 모든 마알을 하나의 칸에 모으려고 한다. 한 번에는 마알 하나만 움직일 수 있으며, 이동 중이거나 이동이 끝난 뒤 같은 칸에 여러 마알이 있어도 된다.
모든 마알을 한 칸에 모으는 데 필요한 이동 횟수의 최솟값을 구하라.
입력
첫째 줄에 체스판의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 체스판의 상태가 위쪽 행부터 순서대로 주어진다. 각 행은 공백 없이 길이 M의 문자열로 주어진다.
빈 칸은 .으로 표시된다. 숫자 K는 그 칸에 K-마알이 놓여 있음을 뜻한다. 입력에는 하나 이상의 마알이 포함된다.
출력
모든 마알을 하나의 칸에 모으기 위해 필요한 이동 횟수의 최솟값을 출력한다. 모든 마알을 한 칸에 모을 수 없다면 -1을 출력한다.
제한
- 1 ≤ N, M ≤ 10
- 각 마알의 K는 1 이상 9 이하의 정수이다.