시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 152 27 15 15.464%

문제

얼마 전 대통령 선거를 한 월드나라는 선거 조작 의혹으로 12개의 소국가로 나누어졌다.


제 1국. Noisulagem, 최백준에 의해 세워진 국가로 월드를 전혀 계승하고 있지 않다.

제 2국. WonderGirls, 신동혁에 의해 세워진 국가다. 소희의 남자친구에 의해 세워진 국가로, 5명의 여왕과, 1명의 왕이 존재하는 왕족국가이다.

제 3국. SoSiNine, 양항승이 소녀시대 9명을 모두 납치해서 만든 국가이다. 양항승 국왕에 의해 통치되는 국가이다. 효연을 제외한 나머지 멤버는 지하감옥에 갇혀 언제 죽을지만 기다리는 삶을 살고 있고, 효연은 양항승의 부인으로 살고 있다.

제 4국. ODuck^2, 오직 오타쿠를 위한 국가이다. 이 나라의 비자를 받으려면, 미연시 오타쿠 테스트와, 일본애니 테스트에서 모두 만점을 받아야지만 가능하다. 언어로는 일본어를 쓰고 있다. おたく ふぃえちん。

제 5국. SocWorld, 월드에서 위닝을 지던 사람들이 만든 국가로, 해외 축구리그를 좋아한다. 현재 축구리그의 활성화방안이 국가 제 1정책이며, 해외 리그의 여러 선수를 막강한 오세준의 자금으로 사드리려고 한다. 위닝 개발자가 이 나라에 납치되어 있다.

제 6국. AntiSJ, 오세준을 라이벌로 생각하는 성혁화가 세운 국가이다. 가위바위보 할 때, 이기지도 않았으면서 먼저 좋아하고 보는 사람만이 비자를 받을 수 있다.

제 7국. 허경영공화국, 허경영이 암살당한 직후, 그 뒤를 이은 오민식이 세운 국가이다. 현재 허경영을 국가 원수로 하는 북한식 국가이고, 새마을 운동을 매일 아침 해야한다. 결혼을 하면 1억을 주고, 아이를 낳으면 5천만원을 준다. 돈을 뿌리는 국가로, 현재 인플레이션이 진행중이며, 화장실에서 돈을 휴지대신 쓴다.

제 8국. 김치국, 오직 김치만 먹는 나라. 설명이 필요없다.

제 9국. HHComeOn, 이정문에 의해 세워진 국가로 힙합이 난무한다.

제 10국. FTZ, 판타지 소설을 매일 읽어야 한다. 학교에서 판타지 소설을 읽지 않으면 맞는다. 수능시험은 판타지 소설을 박종현이 만족할 정도로 써야지, 판타지 대학교에 입학할 수 있다.

제 11국. EZ2DJ, 오직 건반게임만을 할 수 있다. 스타를 하면 사형. 악덕 국왕 임현수에 의해 많은 사람들이 죽고 있다. 매일 밤 자신과 EZ2DJ를 대결할 사람을 구한 뒤, 자신보다 잘하지 못하면 그 자리에서 처형하는 나라로 유명하다. 이 나라는 매일 1명씩 사라지기 때문에, 다른 나라에서 납치를 해오는 나라이다.

제 12국. 테디, 듣보잡.

서로 독자적으로 잘 살고 있던 월드는 오영식의 침략을 받게 되었다. 오영식은 월드를 점령할 목적으로 레이스와, 배틀, 발키리, 사이언스 배슬, 마린, 파이어뱃, 고스트, 메딕, SCV를 포함한 130부대를 데리고 오기 시작했다.

여러 국가의 상위 지도계층들은 서로 긴급 회의를 하려고 한다. 월드는 체스판처럼 이루어져있다고 가정한다.

지도계층들은 교통수단인 마알을 타고 간다. 마알은 1-마알부터 9-마알 까지 있다. 마알은 체스판에서 말처럼 움직일 수 있으며, K-마알은 한번에 K번을 연속으로 움직일 수 있다.

체스판이 주어졋을과, 각각의 K-마알의 위치가 주어졌을 때, 서로 한곳에 모일 수 있는 최소 이동횟수를 구하는 프로그램을 작성하시오. 각 말들은 동시에 같은 곳에 있을 수도 있다.

입력

첫째 줄에 체스판의 세로 크기 N, 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판은 .과 1-9 숫자로만 이루어져있다. .은 빈칸이란 뜻이고, 1-9숫자가 되어 있는 칸은 각각의 마알이 있다는 소리다.

출력

모든 마알의 이동 횟수의 합의 최소값을 출력한다. 한곳에 모일 수 없다면, -1을 출력한다.

예제 입력

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

예제 출력

2

힌트

2-마알이 (2,0)에서 (0,1)로 한번에 움직이고, (0,1)->(2,2)->(0,3)으로 움직이면 총 2번만에 이동할 수 있다.

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: mendou12