치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

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

int n, m;

int arr[51][51];


vector<pair<int, int>>store;
vector<pair<int, int>>houses;

int minnum = 1e9 + 1;

void checkDistance(int x, int y, vector<vector<int>>&check) {
	

	for (auto it : houses) {
		int n = abs(it.first - x) + abs(it.second - y);

		if (check[it.first][it.second] == 0) {
			check[it.first][it.second] = n;
		}
		if (check[it.first][it.second] > n) {
			check[it.first][it.second] = n;
		}

	}
	
}

int getSum(vector<vector<int>>&check) {

	int sum = 0;

	for (int i = 0; i < houses.size(); i++) {
			
		int x = houses[i].first;
		int y = houses[i].second;

		sum += check[x][y];
		
	}

	return sum;
		
}

void chickenRoad(int idx, int count, vector<vector<int>>&check) {
	
	if (count == m) {

		int sum = getSum( check);
	//	cout << sum << endl;

		if (sum < minnum) {
		
			minnum = sum;
		}

		return;
	}

	vector<vector<int>>originCheck = check;
	
	for (int i = idx; i < store.size(); i++) {
		
			
		checkDistance(store[i].first,store[i].second , check);
		chickenRoad(i + 1, count + 1, check);
		check = originCheck;
	}


}


int main() {
	
	cin >> n;
	cin >> m;


	vector<vector<int>>check(51, vector<int>(51, 0));


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			
			cin >> arr[i][j];
			if (arr[i][j]==2) {
				store.push_back(make_pair(i,j));
			}
			else if (arr[i][j] == 1) {
				houses.push_back(make_pair(i, j));
			}
		
		}
	}

	chickenRoad(0, 0, check);
	cout << minnum << endl;




}