복제 로봇

세준이는 자기 자신을 원하는 수만큼 복제할 수 있는 로봇을 만들었다. 복제 장치는 로봇의 시작 위치와 각 열쇠가 놓인 위치에만 설치되어 있다.

N × N 정사각형 미로와 M개의 열쇠 위치, 그리고 로봇의 시작 위치가 주어진다. 모든 열쇠를 찾을 때까지 모든 로봇이 움직인 횟수의 총합이 최소가 되도록 하라.

로봇은 한 번에 상하좌우로 인접한 칸으로 이동할 수 있다. 어떤 로봇이 열쇠가 있는 칸에 도착하면 그 열쇠를 찾은 것으로 본다. 한 칸에 여러 로봇이 동시에 있어도 되며, 이미 지나간 칸을 다른 로봇이나 같은 로봇이 다시 지나가도 된다. 복제에는 시간이 들지 않는다. 모든 열쇠를 찾은 뒤 로봇들이 같은 위치로 모일 필요는 없다.

첫째 줄에 미로의 크기 N과 열쇠의 개수 M이 공백으로 구분되어 주어진다. (4 ≤ N ≤ 50, 1 ≤ M ≤ 250)

다음 N개의 줄에는 미로 정보가 주어진다. 각 문자는 1, 0, S, K 중 하나이다.

• 1: 벽
• 0: 이동할 수 있는 길
• S: 로봇의 시작 위치
• K: 열쇠의 위치

S는 정확히 1개, K는 정확히 M개 주어진다. 복제는 S와 K가 있는 칸에서만 할 수 있다. 미로의 모든 테두리는 벽이다.

모든 열쇠를 찾기 위해 모든 로봇이 움직인 횟수의 최소 총합을 출력한다. 모든 열쇠를 찾을 수 없다면 -1을 출력한다.