#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

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

int N, M;

int calc(vector<pair<int, int>> chickens)
{
    int sum = 0;
    // 각각의 집에 대해 최단 치킨 거리를 구한다.
    for(auto o : houses)
    {
        int min_ = 1000000;
        for(auto p : chickens)
        {
            min_ = min(min_, abs(o.first-p.first) + abs(o.second - p.second));
            if(min_==1)break;
        }
        sum += min_;
        // 구한 결과를 반환한다.
    }
    return sum;  
}

// 조합적으로 겹치는 경우
// 벡터에 {1, 2, 3, 4, 5} 있는 경우랑
// {2, 1, 3, 4, 5} 있는 경우.. 모두 다른 케이스로 들어간다..

int dfs(vector<pair<int, int>> chickens, int level, bool visited[],int id)
{
    if(level == M) // M 개를 골랐다!
    {
        int a = calc(chickens);
        // cout << a << " ";
        return a;
    }
    // int sz = chickens.size();
    int min_ = 100000;
    for(int i=id; i<total_chickens.size(); i++)
    {
        if(!visited[i])
        {
            // pair<int, int> tmp = chickens.at(i);
            chickens.push_back(total_chickens.at(i));
            visited[i] = true;
            min_ = min(min_, dfs(chickens, level+1, visited, id+1));
            chickens.pop_back();
            visited[i] = false;
        }
    }
    return min_;
}

int main()
{
    // N x N의 도시. (맵 형태.)
    // 각 칸은 빈 칸, 치킨집, 집 (3개) 중 하나다. 도시는 (r,c)=(행,열)
    // 1부터 시작함.
    // 치킨 거리 = 집과 가장 가까운 치킨집 가시의 거리임.
    // 모든 집의 치킨 거리의 합..
    // 맨하탄 거리로 계산한다.

    // 0=빈칸, 1=집, 2=치킨집

    // 치킨집 중 M개 빼고 없앤 후, 치킨 거리 최소되도록 하기.
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;

    int tmp;
    int cnt=0;

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> tmp;
            if (tmp == 1)
            {
                houses.push_back(make_pair(i, j));
            }
            else if(tmp == 2)
            {
                total_chickens.push_back(make_pair(i, j));
            }
        }
    }
    bool *visited = new bool[total_chickens.size()];
    for(int i=0; i<total_chickens.size(); i++)
    {
        visited[i] = 0;
    }
    int level = 0;
    vector<pair<int, int>> chickens;

    cout << dfs(chickens, level, visited, 0);
}


예제는 다 맞는데 시간초과 ㅇㅅㅇ;;