C++/Solve & Think
백준_15686번_치킨 배달
안댕
2020. 10. 8. 01:25

소스코드
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
int result = INT_MAX;
int N, M;
int calcDistance(vector<pair<int, int>> t_chicken) {
int total = 0;
for (int i = 0; i < house.size(); i++) {
int distance = INT_MAX;
for (int j = 0; j < t_chicken.size(); j++) {
distance = min(distance,
abs(t_chicken[j].first - house[i].first) + abs(t_chicken[j].second - house[i].second));
}
total += distance;
}
return total;
}
void dfs(int idx, vector<pair<int, int>> t_chicken) {
if (t_chicken.size() == M) {
result = min(calcDistance(t_chicken), result);
return;
}
for (int start = idx; start < chicken.size(); start++) {
t_chicken.push_back(chicken[start]);
dfs(start + 1, t_chicken);
t_chicken.pop_back();
}
}
int main() {
int t;
cin >> N >> M;
vector<pair<int, int>> t_chicken;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> t;
if ( t == 1)
house.push_back(make_pair(i,j));
if ( t == 2)
chicken.push_back(make_pair(i, j));
}
}
dfs(0, t_chicken);
cout << result << endl;
return 0;
}