백준 15686번 치킨 배달 ( C++ )

문제

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

15686번: 치킨 배달

 

해설

완탐 / 백트래킹 문제

조합 함수만 잘 만들면 어렵지 않은 문제

 

코드

#include <bits/stdc++.h>
using namespace std;
int n, m, r, c, tmp;
vector<pair<int, int>> chickenAll, home;
// vector<vector<int>> chicken;
int ret = 100000000;
int check1(vector<int> v)
{
  int cnt = 0;
  for (pair<int, int> location : home)
  {
    int mn = 2 * n;
    for (int i : v)
    {
      mn = min((abs(location.first - chickenAll[i].first) + abs(location.second - chickenAll[i].second)), mn);
    }
    cnt += mn;
  }
  return cnt;
}
 
void combi(int cnt, vector<int> v)
{
  if (v.size() == m)
  {
    ret = min(check1(v), ret);
    return;
  }
 
  for (int i = cnt; i < chickenAll.size(); i++)
  {
    v.push_back(i);
    combi(i + 1, v);
    v.pop_back();
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> n >> m;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> tmp;
      if (tmp == 2)
        chickenAll.push_back({i, j});
      else if (tmp == 1)
        home.push_back({i, j});
    }
  }
 
  vector<int> v;
  combi(0, v);
  cout << ret;
}