[골5] 15686 - 치킨 배달

#include <limits.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

using IntPair = pair<int, int>;

#define y first
#define x second

vector<vector<int>> board;
vector<IntPair> house, chicken;
int m, n, res = 0;
bool vis[13];

int distance(IntPair a, IntPair b) { return abs(a.y - b.y) + abs(a.x - b.x); }

void DFS(int start = 0, int end = 0)
{
    if (end == m)
    {
        int tmpRes = 0;

        for (int i = 0; i < house.size(); i++)
        {
            int dist = INT_MAX;

            for (int j = 0; j < chicken.size(); j++)
            {
                if (vis[j])
                    dist = min(dist, distance(house[i], chicken[j]));
            }
            tmpRes += dist;
        }
        res = min(res, tmpRes);
        return;
    }
    if (start == chicken.size())
        return;

    vis[start] = true;
    DFS(start + 1, end + 1);

    vis[start] = false;
    DFS(start + 1, end);
}

int main() 
{
    //무방향성
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    board = vector<vector<int>>(n, vector<int>(n));

    for (int y = 0; y < n; y++)
    {
        for (int x = 0; x < n; x++)
        {
            cin >> board[y][x];
            auto num = board[y][x];
            IntPair pos{ y,x };

            if (num == 1)
                house.push_back(pos);

            else if (num == 2)
                    chicken.push_back(pos);
        }
    }
    res = INT_MAX;
    DFS();
    cout << res;
    return 0;
}