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

質問リンク:https://www.acmicpc.net/problem/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個の休業しないフライドチキン店を選ぶと、都市フライドチキン街の最高価格が出力されます.

問題を理解する

地図を提供し、フライドチキン屋と家の位置を提供します.フライドチキン店のいくつかが休業します.入力した数字で廃業していたら、どのチキン屋が廃業するのかというと、チキン屋と家の間の距離が最小の問題です.
これは組み合わせの問題です.
フライドチキン屋では、入力数に応じて選択し、選んだフライドチキン屋と家から近いフライドチキン屋を探します.すべてのものを最短距離の和を繰り返し求めればいい.

質問へのアクセス

入力

に入力された数字を組み合わせます.

セットで獲得したチキン屋と家との最小距離の和.

までの最小距離の和と現在求められている最小距離の和を比較する.

2-4回繰り返します.

コード実装（C++）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int maxChicken;
vector<pair<int, int> > home;
vector<pair<int, int> > chickenHouse;
vector<int> selectedCHouse;
int selectedChicken[13] = {false, };
int dist[100];
int minDist = 987654321;

void calDist(){
    for(int i = 0 ; i < maxChicken ; i++){
        int temp = selectedCHouse[i]; 
        
        for(int j = 0 ; j < home.size() ; j++){
            int tempDist = abs(chickenHouse[temp].first - home[j].first) + abs(chickenHouse[temp].second - home[j].second);
            if(dist[j] == -1 || dist[j] > tempDist) dist[j] = tempDist; 
            
        }
    }
    int sumDist = 0;
    for(int i = 0 ; i < home.size() ; i++){
        sumDist += dist[i];
    }
    minDist = min(minDist, sumDist);
}

void combination(int num, int cnt){
    if(cnt == maxChicken){
        calDist();
        memset(dist,-1,sizeof(dist));
    }
    else{
        for(int i = num ; i < chickenHouse.size() ; i++){
            if(!selectedChicken[i]){
                selectedChicken[i] = true;
                selectedCHouse.push_back(i);
                combination(i, cnt+1);
                selectedCHouse.pop_back();
                selectedChicken[i] = false;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> N >> maxChicken;
    int temp;
    int count = 0;
    memset(dist, -1, sizeof(dist));
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> temp;
            if(temp == 1) home.push_back(make_pair(i,j));
            else if(temp == 2) chickenHouse.push_back(make_pair(i,j));
        }
    }
    combination(0,0);
    cout << minDist << "\n";
}

評価

コードがきれいに実現されていないと思います.変数が多すぎる.早めにつけないと混乱しますよmemsetは-1と0しか入力できません.
アルゴリズムタイトルのfillを使用して、必要な数値を入力します.