https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 54;
int n, m;
int map[MAX][MAX];
vector<pair<int, int>> store;
vector<pair<int, int>> house;
vector<pair<int, int>> selects;
int answer = 987654321;
void CalWay() {
int tmp_ans = 0;
for (int i = 0; i < house.size(); i++) {
int way = 987654321;
int x = house[i].first;
int y = house[i].second;
for (int j = 0; j < selects.size(); j++) {
int x2 = selects[j].first;
int y2 = selects[j].second;
int v = abs(x- x2) + abs(y - y2);
way = min(way, v);
}
tmp_ans += way;
}
answer = min(answer, tmp_ans);
}
void FindStore(int index) {
if (selects.size() == m) {
CalWay();
return;
}
for (int i = index; i < store.size(); i++) {
selects.push_back(store[i]);
FindStore(i + 1);
selects.pop_back();
}
}
int main(void) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> map[i][j];
if (map[i][j] == 2) {
store.push_back({ i,j });
}
else if (map[i][j] == 1) {
house.push_back({ i,j });
}
}
}
FindStore(0);
cout << answer << endl;
}