[白俊C+]15686フライドチキン出前

質問する

サイズN×N人の町があります.都市は1×一つの大きさの格子に分ける.都市のどの部屋も空き部屋、フライドチキン屋、家の一つです.都市のセルは(r,c)と同じ形式で表示され、r行c列または上からr列、左からc列を表す.rとcは1から始まる.
この町に住んでいる人はチキンが大好きです.そのため、主に「チキンストリート」という言葉が使われています.フライドチキン街は家と一番近いフライドチキン屋の間の距離です.つまり、フライドチキン街は家を基準に定められており、どの家にもフライドチキン街があります.都市のフライドチキン街はすべての家のフライドチキン街の総和です.
任意の2つのセル(r 1,c 1)と(r 2,c 2)との間の距離を|r 1−r 2|+|c 1−c 2|で表す.
例えば、以下の地図がある都市を見てみましょう.
0は空き部屋、1は家、2はチキン屋です.
(2,1)上の家と(1,2)上のフライドチキン屋の距離は|2-1|+|1-2|=2,(5,5)上のフライドチキン屋の距離は|2-5|+|1-5|=7である.ということで、(2,1)家のチキンストリートは2.
(5,4)上の家と(1,2)上のフライドチキン屋の距離|5-1|+|4-2|=6、(5,5)上のフライドチキン屋の距離|5-5|+|4-5|=1.ということで、(5,4)家のチキンストリートは1.
この町のフライドチキン屋は同じチェーン店です.チェーン店本社は収益を上げるため、フライドチキン店の一部を閉鎖する計画だ.長い研究を経て、この都市で最もお金を稼ぐフライドチキン店はM社が最も多いことが分かった.
都市部のフライドチキン店ではM社が最も多く、残りのフライドチキン店は休業する.どのように選ぶか、都市のフライドチキン街が一番小さいかを求めるプログラムを作成してください.

入力

第1行はN(2≦N≦50)とM(1≦M≦13)を与える.
2行目からN行は都市の情報を与えている.
都市の情報は0,1,2で構成され,0はスペース,1は家,2はフライドチキン店である.家の数は2 Nを超えず、少なくとも1つ存在する.フライドチキン店の個数はM以上、13未満である.

しゅつりょく

1行目で最大M個の休業しないフライドチキン店を選ぶと、都市フライドチキン街の最高価格が出力されます.
https://www.acmicpc.net/problem/15686

に答える

あげた唐揚げセットは、m個のみ、
すべての家で選択したm個のリストでフライドチキン距離を計算し、
全部合わせて都市のチキン街の価格を求めればいいです.

で使用される変数

軒、chicken:家とフライドチキン店の位置座標記録

ピックアップ:m個のフライドチキン店の位置を再帰的に選択する際に使用するインデックス配列

chooseChickenList:m個選択したchooseを配列保存リストに置き換える

入力部
店とフライドチキン店の位置をベクトルに記録します

pick:n個(入力したnとは異なる)のフライドチキンセットcnt個の関数

cntは再帰的に呼び出され、1つずつ減少し、0になった瞬間にcnt犬が選択され、int[]で選択された配列chooseChickenListを弁護し、chooseChickenListに追加する.

calculateCD:家屋座標x 1,y 1からm個のフライドチキン店のリストの中で最も短い距離の.この家のフライドチキンの距離値を求めることで返す関数です.

3号で作ったフライドチキンカタログを回り、すべての家のフライドチキンの距離価格を合計(4号)し、その中で最も高い価格を探しています.

最終最小値は都市フライドチキン距離値、出力

問題はメモリに大きな制限はありませんが、ベクトル記録家やフライドチキン店の座標の方法でメモリを最小限に抑えることができます.残念なことに、calculateCDの3番目のパラメータも参照変数として書き込みを宣言しようとしましたが、アクセス方法が分からないのでポインタを使用しました.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::pair;
int n, m;
vector<pair<int, int>> home, chicken;
vector<int> picked; 
vector<int*> chooseChickenList; //m개를 선택한 리스트들을 담음
void func();
void pick(int n, vector<int>& picked, int cnt);
int calculateCD(int x1, int y1, int* list);

void func() {
	pick(chicken.size(), picked, m); //치킨집중 m개를선택한 리스트쌍을 만든다.
	int res = 0x7fffffff;
	for (int i = 0; i < chooseChickenList.size(); i++) { //선택된 m개의 치킨집 의 리스트를
		int sum_CD = 0; //m개 고른 치킨집들에대한 모든 집의 치킨거리를 합산
		for (int j = 0; j < home.size(); j++) { //모든집에대해 탐색
			int CD = calculateCD(home[j].first, //현재 집의
								home[j].second, //치킨거리를 구함
						chooseChickenList[i]);
			sum_CD += CD; 
		}
		if (res > sum_CD) res = sum_CD; //도시의 치킨거리의 최솟값만 기록
	}
	printf("%d", res); //출력
}

void pick(int n, vector<int>& picked, int cnt) {
	if (cnt == 0) {//뽑힌것에대해 뭘하실.
		int* l = new int[picked.size()];
		for (int i = 0; i < picked.size(); i++)
			l[i] = picked[i];
		chooseChickenList.push_back(l); //선탟한 치킨목록에 추가
		return;
	}
	int smallest = picked.empty() ? 0 : picked.back() + 1;
	for (int i = smallest; i < n; i++) {
		picked.push_back(i); //picked 넣고
		pick(n, picked, cnt - 1);
		picked.pop_back(); //picked를 빼면서 다음 요소를 참조.
	}
}

//해당 집의 치킨거리를 구하는 함수
int calculateCD(int x1, int y1, int* list) {
	int res=0x7fffffff ,x2, y2;
	for (int i = 0; i < m; i++) { //m개의 치킨집을 탐색
		x2 = chicken[list[i]].first;
		y2 = chicken[list[i]].second;
		int d = (x2 < x1 ? x1 - x2 : x2 - x1) + 
			(y2 < y1 ? y1 - y2 : y2 - y1);
		if (res > d) res = d; //최소거리만 기록
	}
	return res;
}

int main(void) {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0, temp; j < n; j++) {
			scanf("%d", &temp);
			if (temp == 1) 
				home.push_back({i, j}); //집위치 저장
			else if (temp == 2) 
				chicken.push_back({ i, j }); //치킨집위치 저장
		}
	}

	func();

	return 0;
}