치킨 배달

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<pair<int, int> > hs;
vector<pair<int, int> > chick;
int ans = 2147000000;
int ch[14];

void DFS(int D, int cnt) {
	if (D > chick.size()) return;
	if (cnt == m) {
		int sum = 0;
		for (int i = 0; i < hs.size(); i++) {
			int dist = 2147000000;
			int hs_y = hs[i].first;
			int hs_x = hs[i].second;
			for (int j = 0; j < m; j++) {
				int chick_y = chick[ch[j]].first;
				int chick_x = chick[ch[j]].second;
				dist= min(dist, abs(hs_y - chick_y) + abs(hs_x - chick_x));
			}
			sum += dist;
		}
		ans = min(ans, sum);
	}
	else {
		ch[cnt] = D;
		DFS(D + 1, cnt + 1); //해당 치킨집 선정
		DFS(D + 1, cnt); // 해당 치킨집 미선정
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= n; x++) {
			int num;
			cin >> num;
			if (num == 1) hs.push_back(make_pair(y, x));
			if (num == 2) chick.push_back(make_pair(y, x));
		}
	}
	DFS(0, 0);
	cout << ans << "\n";
	return 0;
}