Boj15686_치킨 배달

Published: December 04, 2018 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

boj15686_치킨 배달

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

struct homeinfo {
	int x, y, len, idx;
};
vector<homeinfo> h;
vector<pair<int, int>> c;
int num, n, m, list[13];

int go(int idx, int lastidx) {
	if (idx == m) {
		int res = 0;
		for (int i = 0; i < h.size(); i++) {
			int dist = 1e9;
			for (int j = 0; j < idx; j++) {
				dist = min(dist, abs(h[i].x - c[list[j]].first) + abs(h[i].y - c[list[j]].second));
			}
			res += dist;
		}
		return res;
	}
	int res = 1e9;
	for (int i = lastidx; i < c.size(); i++) {
		list[idx] = i;
		res = min(res, go(idx + 1, i + 1));
	}
	return res;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &num);
			if (num == 1)h.push_back({ i,j,(int)1e9,(int)1e9 });
			if (num == 2) c.push_back({ i,j });
		}
	}

	printf("%d", go(0, 0));

}