15686 치킨 배달

문제 - 치킨 거리란 집에서 가장 가까운 치킨까지의 거리로 도시는 격자형태로 되어 있다. 예를 들어 2,1에 집이있고 3,2에 치킨집이 있으면
치킨 거리 : |2-3| + |1-2| = 2 이다.
모든 집에서 치킨집까지의 거리가 최소가 되도록 치킨집을 최대 m개 고르도록 하자.

입력

• n(전체 입력의 크기-n x n)
• m(치킨집 최대 개수)
• n x n 의 도시 정보

출력

• 해당 도시에서 가능한 모든 치킨 거리의 합 중 가장 짧은 치킨 거리의 합을 출력

도시 정보의 최대 사이즈가 50x50이고 치킨집이 최대 등장가능한 수가 13개이므로 n과m문제처럼 여러 조합을 만들어내고 거기다가 거리를 찾기만 하면 되는 문제였다.

정답 코드

#include<iostream>
#include<vector>
#include<utility>

#define MAX 99999999

using namespace std;

vector<pair<int, int>>chicken;
vector<pair<int, int>>house;
int map[50][50];
int minidistance = MAX;
int n, m, c;
int arr[13][2];
bool visit[13];

int absol(int a) {
	if (a < 0)
		return a * -1;
	else
		return a;
}

void search(int i,int j) {
	if (j >= m) {
		int r = 0;
		for (auto p : house) {
			int mini = MAX;
			for (int q = 0; q < j; q++) {
				int cup = absol(p.first - arr[q][0]) + absol(p.second - arr[q][1]);
				mini = min(cup, mini);
			}
			r += mini;
		}
		minidistance = min(r, minidistance);
		return;
	}
	for (int p = i; p < c; p++) {
		if (!visit[p]) { 
			visit[p] = 1;
			arr[j][0] = chicken[p].first;
			arr[j][1] = chicken[p].second;
			search(p + 1, j + 1);
			visit[p] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1)house.push_back(make_pair(i, j));
			else if (map[i][j] == 2)chicken.push_back(make_pair(i, j));
		}
	}
	c = chicken.size();
	search(0, 0);

	cout << minidistance;

	return 0;
}