CS106B(2022 winter) hw4

重生之你在美国当总统

题目描述

We'll say that a country is disaster-ready if every city either already has emergency supplies or is immediately down the highway from a city that has them. Your task is to write a function

bool canBeMadeDisasterReady(const Map<string, Set<string>>& roadNetwork,
                            int numCities,
                            Set<string>& supplyLocations);

takes as input a Map representing the road network for a region and the number of cities you can afford to put supplies in, then returns whether it's possible to make the region disaster-ready without placing supplies in more than numCities cities. If so, the function should then populate the argument supplyLocations with all of the cities where supplies should be stored.

代码

bool canBeMadeDisasterReadyHelper(const Map<string, Set<string>>& roadNetwork,
                                  int numCities,
                                  Set<string>& supplyLocations,Set<string>& unreadyCities){
    if(roadNetwork.size() == 0) return true;

    if(unreadyCities.size() == 0)  return true;
    else if(numCities <= 0) return false;

    //stockpile in it
    string city = unreadyCities.first();
    supplyLocations.add(city);

    Set<string> remainingCities = unreadyCities - city - roadNetwork[city];

    bool result1 = canBeMadeDisasterReadyHelper(roadNetwork,numCities - 1,supplyLocations,remainingCities);

    if(result1) return result1;
    else supplyLocations.remove(city);

    Set<string> neighborCities = roadNetwork[city];
    for(const string &neighbor:neighborCities){

        supplyLocations.add(neighbor);
        Set<string> remainingCities = unreadyCities - neighbor - roadNetwork[neighbor];
        bool result2 = canBeMadeDisasterReadyHelper(roadNetwork,numCities - 1,supplyLocations,remainingCities);
        if(result2) return result2;
        else supplyLocations.remove(neighbor);
    }
    return false;
}


bool canBeMadeDisasterReady(const Map<string, Set<string>>& roadNetwork,
                            int numCities,
                            Set<string>& supplyLocations) {
    /* TODO: Delete the next few lines and implement this function. */
    if(numCities < 0) error("error");
    Set<string> unreadyCities;
    for(const string &city : roadNetwork){
        unreadyCities.add(city);
        Set<string> neighborCities = roadNetwork[city];
        for(const string &s: neighborCities){
            unreadyCities.add(s);
        }
    }

    return canBeMadeDisasterReadyHelper(roadNetwork,numCities,supplyLocations,unreadyCities);
}

后记

自己的思路是用Map<string,int>来存储每个城市的状态，但是一直有bug，看了知乎某个大佬的解答才转换了思路。