15686 Samsung sw test
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#define MAX_WIDTH 50
#define MAX_CHIKEN 13
using namespace std;
typedef struct Location {
int row;
int col;
} Location;
int width, maxChiken, numOfHouse, numOfChiken;
Location house[2 * MAX_WIDTH];
Location chiken[MAX_CHIKEN];
int minDistance = 10000000;
int index[MAX_CHIKEN];
void findMinChikenDistance(int deep = 0, int len = 0);
int main() {
cin >> width >> maxChiken;
for (int i = 0; i < width; i++) {
for (int j = 0; j < width; j++) {
int temp;
cin >> temp;
if (temp == 1)
house[numOfHouse++] = { i, j };
else if (temp == 2)
chiken[numOfChiken++] = { i, j };
}
}
findMinChikenDistance();
cout << minDistance;
}
void findMinChikenDistance(int deep, int len) {
if (len == maxChiken) {
//검사
int distance = 0;
for (int h = 0; h < numOfHouse; h++) {
int min = 100000000;
for (int c = 0; c < maxChiken; c++) {
int rowD = house[h].row - chiken[index[c]].row;
int colD = house[h].col - chiken[index[c]].col;
rowD = rowD < 0 ? (-1) * rowD : rowD;
colD = colD < 0 ? (-1) * colD : colD;
min = (rowD + colD) < min ? (rowD + colD) : min;
}
distance += min;
}
minDistance = distance < minDistance ? distance : minDistance;
return;
}
if (numOfChiken - deep < maxChiken - len)
return;
index[len] = deep;
findMinChikenDistance(deep + 1, len + 1);
findMinChikenDistance(deep + 1, len);
}