풀이
#include <iostream>
#include <math.h>
using namespace std;
typedef struct point{
int x;
int y;
} point;
int N, M;
int map[51][51];
point house[101];
point chick[14];
int num_house = 0, num_chick = 0;
int is_open[14];
int rst = 100000;
point make_point(int x, int y);
void dfs(int m, int depth);
int cal_distance(int x1, int y1, int x2, int y2);
int get_min_distance();
point make_point(int x, int y);
int main(){
cin >> N >> M;
for(int i = 1; i <= N; i++){
for(int j = 1 ; j <= N; j++){
cin >> map[i][j];
if(map[i][j] == 1){
house[++num_house] = make_point(i, j);
} else if(map[i][j] == 2){
chick[++num_chick] = make_point(i, j);
}
}
}
for(int i = 1; i <= num_chick; i++) dfs(i, 1);
cout << rst << endl;
}
void dfs(int m, int depth){
is_open[m] = 1;
if(depth == M){
int d = get_min_distance();
if(rst > d) rst = d;
is_open[m] = 0;
return ;
}
for(int i = m + 1; i <= num_chick; i++){
dfs(i, depth + 1);
}
is_open[m] = 0;
}
int cal_distance(int x1, int y1, int x2, int y2){
return abs(x1 - x2) + abs(y1 - y2);
}
int get_min_distance(){
int sum = 0;
for(int h = 1; h <= num_house; h++){
int min_d = 100000;
for(int c = 1; c <= num_chick; c++){
if(is_open[c]){
int curr_d = cal_distance(house[h].x, house[h].y, chick[c].x, chick[c].y);
if(min_d > curr_d) min_d = curr_d;
}
}
sum += min_d;
}
return sum;
}
point make_point(int x, int y){
point p;
p.x = x; p.y = y;
return p;
}