백준 15686번 : 치킨 배달

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

int getChickenDistance(const vector<pair<int, int>>& houses, const vector<pair<int, int>>& selectedChicken) {
    int totalDistance = 0;

    for (const auto& house : houses) {
        int minDistance = INT_MAX;
        for (const auto& shop : selectedChicken) {
            minDistance = min(minDistance, abs(house.first - shop.first) + abs(house.second - shop.second));
        }
        totalDistance += minDistance;
    }
    return totalDistance;
}

void selectChicken(int N, int M, int index, const vector<pair<int, int>>& chicken, vector<pair<int, int>>& selectedChicken, const vector<pair<int, int>>& houses, int& result) {
    if (selectedChicken.size() == M) {
        result = min(result, getChickenDistance(houses, selectedChicken));
        return;
    }

    for (int i = index; i < chicken.size(); i++) {
        selectedChicken.push_back(chicken[i]);
        selectChicken(N, M, i + 1, chicken, selectedChicken, houses, result);
        selectedChicken.pop_back();
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<pair<int, int>> houses, chicken;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int value;
            cin >> value;
            if (value == 1) {
                houses.push_back({i, j});
            } else if (value == 2) {
                chicken.push_back({i, j});
            }
        }
    }

    int result = INT_MAX;
    vector<pair<int, int>> selectedChicken;
    selectChicken(N, M, 0, chicken, selectedChicken, houses, result);
    cout << result << endl;

    return 0;
}