우편 수거함 줄이기

문제

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

5

5 2
2 2 2 2 0
0 0 2 2 0
2 0 0 2 0
1 0 2 0 0
1 2 0 0 0

2

2 1
1 2
2 1

2

입력 조건

• 가장 먼저 첫째 줄에 마을의 한 변의 칸 수 N과 남길 수거함의 개수 M이 공백을 두고 주어진다. N은 2 이상 50 이하의 자연수이고, M은 1 이상 13 이하의 자연수다.

• 이어서 N개의 줄에 걸쳐 마을의 각 행의 정보가 위쪽 행부터 차례대로 주어진다. 각 줄에는 N개의 수가 공백을 두고 주어지며, 0은 빈 땅, 1은 집, 2는 우편 수거함을 뜻한다.

• 마을의 집은 1개 이상 100개 이하이고, 수거함은 1개 이상 13개 이하다. 또한 M은 마을에 있는 수거함의 개수보다 크지 않다.

출력 조건

• 수거함 M개를 남기는 모든 방법 가운데, 마을의 수거함 거리가 가장 작아지는 경우의 그 값을 첫째 줄에 출력한다. 출력하는 값은 거리의 합이므로 0 이상의 정수다.

요구사항

• 두 칸 사이의 거리는 행 번호 차이와 열 번호 차이를 더한 값입니다
• 한 집의 수거함 거리는 남아 있는 수거함까지의 거리 가운데 가장 작은 값입니다
• 마을의 수거함 거리는 모든 집의 수거함 거리를 더한 값입니다
• 수거함은 정확히 M개를 남깁니다
• 집은 치우지 않으며, 마을의 모든 집을 계산에 넣습니다
• 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
• 쓸 수 있는 말은 파이썬, 자바스크립트입니다
• 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
• 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
• 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
• 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
• 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
• 케이스 15개를 전부 통과해야 해결입니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

2 1
1 2
2 1

2

5 2
2 2 2 2 0
0 0 2 2 0
2 0 0 2 0
1 0 2 0 0
1 2 0 0 0

2

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

5