[白俊]15686号唐揚げ出前(C++、三星基出)

https://www.acmicpc.net/problem/15686
以前に解いた問題はすべてソートされていたので、順番に解いてからタイムアウトしました.
問題をもう一度読んでみると、順序は関係なく、組み合わせで解決しました.

void solve(int idx, int depth, vector<int>& pick) {
	// 최대 개수를 골랐을 때, 거리 계산
	if (pick.size() == m){
		answer = min(answer, get_chicken_distance(pick));
		return;
	}
	// 끝까지 탐색했으면 return
	if (depth == chicken.size()) return;
	vector<int> cp;
	// pick배열 복사
	for (int i = 0; i < pick.size(); i++) cp.push_back(pick[i]);
	cp.push_back(idx);
	// 선택한 것과 선택 안한 것 두개로 나눠서 호출
	solve(idx + 1, depth + 1, cp);
	solve(idx + 1, depth + 1, pick);
}

上のコードはメインコードです.
フライドチキン店の座標を保存するベクトルを回して、フライドチキン店とフライドチキン店を選択しない場合を処理すれば、すべての状況を処理することができます.

完全なコード

#include <iostream>
#include <vector>

using namespace std;

int n, m;
struct p {
public :
	int x; 
	int y;
	p(int x, int y) {
		this->x = x;
		this->y = y;
	}
};
vector<p> house;
vector<p> chicken;
int answer = 987654321;


// 거리 계산
int distance(p a, p b) {
	return abs(a.x - b.x) + abs(a.y - b.y);
}

// 모든 집에 대해서 
// 치킨 거리 계산
int get_chicken_distance(vector<int>& pick) {
	int sum = 0;
	for (int i = 0; i < house.size(); i++) {
		int min_distance = 987654321;
		for (int j = 0; j < pick.size(); j++) {
			min_distance = min(min_distance, distance(chicken[pick[j]], house[i]));
		}
		sum += min_distance;
	}
	return sum;
}


void solve(int idx, int depth, vector<int>& pick) {
	// 최대 개수를 골랐을 때, 거리 계산
	if (pick.size() == m){
		answer = min(answer, get_chicken_distance(pick));
		return;
	}
	// 끝까지 탐색했으면 return
	if (depth == chicken.size()) return;
	vector<int> cp;
	// pick배열 복사
	for (int i = 0; i < pick.size(); i++) cp.push_back(pick[i]);
	cp.push_back(idx);
	// 선택한 것과 선택 안한 것 두개로 나눠서 호출
	solve(idx + 1, depth + 1, cp);
	solve(idx + 1, depth + 1, pick);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int in;
			cin >> in;
			if (in == 1) house.push_back(p(j, i));
			else if (in == 2) chicken.push_back(p(j, i));
		}
	}

	vector<int> pick;
	solve(0, 0, pick);
	cout << answer;
}