[BOJ 15686] 치킨 배달

백준 :: BOJ :: 15686 :: 치킨 배달

출처 : https://www.acmicpc.net/problem/15686

#include <bits/stdc++.h>

using namespace std;

struct s {

int r, c, ch;

};

int N, M, tmp, ans;

vector <s> h, c;

vector<int>a;

vector<vector<int>> hh;

void dfs(int n, int ii) {

if (n == M) {

int r = 0;

for (int i = 0; i < h.size(); i++) {

int rr = 1e9;

for (int j = 0; j < a.size(); j++) {

rr = min(rr, hh[i][a[j]]);

}

r += rr;

}

ans = min(ans, r);

return;

}

for (int i = ii; i < c.size(); i++) {

a.push_back(c[i].ch); dfs(n+1, i + 1); a.pop_back();

}

return;

}

int main() {

std::ios::sync_with_stdio(false); cin.tie(0);

cin >> N >> M; ans = 1e9;

int cnt = 0;

for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {

cin >> tmp; 

if (tmp == 1) h.push_back({ i,j,0 });

else if (tmp == 2) c.push_back({i,j,cnt++});

}

hh.resize(h.size());

int r = 0;

for (int i = 0; i < h.size(); i++) for (int j = 0; j < c.size(); j++) 

hh[i].push_back(abs(h[i].c - c[j].c) + abs(h[i].r - c[j].r));

dfs(0,0);

cout << ans;

return 0;

}