|
|||||||
Время создания: 28.07.2017 16:19
Раздел: Computer - Programming - C++ - Coursera White_Belt
|
|||||||
|
|||||||
Реализуйте систему хранения автобусных маршрутов. Вам нужно обрабатывать следующие запросы:
Формат ввода В первой строке ввода содержится количество запросов Q, затем в Q строках следуют описания запросов. Гарантируется, что все названия маршрутов и остановок состоят лишь из латинских букв, цифр и знаков подчёркивания. Для каждого запроса NEW_BUS bus stop_count stop1 stop2 ... гарантируется, что маршрут bus отсутствует, количество остановок больше 0, а после числа stop_count следует именно такое количество названий остановок, причём все названия в каждом списке различны. Формат вывода Для каждого запроса, кроме NEW_BUS, выведите соответствующий ответ на него:
Предупреждение Условие задачи выше содержит много важных деталей. Если вы не уверены в том, что не упустили ни одной, перечитайте условие ещё раз. Пример Ввод 10 ALL_BUSES BUSES_FOR_STOP Marushkino STOPS_FOR_BUS 32K NEW_BUS 32 3 Tolstopaltsevo Marushkino Vnukovo NEW_BUS 32K 6 Tolstopaltsevo Marushkino Vnukovo Peredelkino Solntsevo Skolkovo BUSES_FOR_STOP Vnukovo NEW_BUS 950 6 Kokoshkino Marushkino Vnukovo Peredelkino Solntsevo Troparyovo NEW_BUS 272 4 Vnukovo Moskovsky Rumyantsevo Troparyovo STOPS_FOR_BUS 272 ALL_BUSES Вывод No buses No stop No bus 32 32K Stop Vnukovo: 32 32K 950 Stop Moskovsky: no interchange Stop Rumyantsevo: no interchange Stop Troparyovo: 950 Bus 272: Vnukovo Moskovsky Rumyantsevo Troparyovo Bus 32: Tolstopaltsevo Marushkino Vnukovo Bus 32K: Tolstopaltsevo Marushkino Vnukovo Peredelkino Solntsevo Skolkovo Bus 950: Kokoshkino Marushkino Vnukovo Peredelkino Solntsevo Troparyovo #include <iostream> #include <vector> #include <string> #include <map> using namespace std; int main() { unsigned int q; vector<string> bus_seq; map<string, vector<string>> buses; cin >> q; while(q) { string command; cin >> command; if(command == "ALL_BUSES") { if(buses.size()) { for(const auto& i : buses) { cout << "Bus " << i.first << ": "; for(const auto j : i.second) cout << j << " "; cout << "\n"; } } else cout << "No buses\n"; } else { string busstop; cin >> busstop; if(command == "STOPS_FOR_BUS") { bool bus_exists = false; unsigned int bus_seq_quantity = bus_seq.size(); for(unsigned int c=0; c<bus_seq_quantity; ++c) { if(bus_seq[c] == busstop) { bus_exists = true; break; } } if(bus_exists) { vector<string> stops = buses[busstop]; vector<string> search; for(const auto& i : stops) { cout << "Stop " << i << ": "; bool doYouFind = false; for(unsigned int j=0; j<bus_seq_quantity; ++j) { if(bus_seq[j] != busstop) //number of bus { search = buses[bus_seq[j]]; //stops for bus bus_seq[j] unsigned int quantity = search.size(); for(unsigned int k=0; k<quantity; ++k) { if(search[k] == i) { doYouFind = true; cout << bus_seq[j] << " "; break; } } } } if(!doYouFind) { cout << "no interchange"; } cout << "\n"; } } else cout << "No bus\n"; /*for(unsigned int i=0; i<quantity; ++i) { cout << buses[busstop].second[i] << " "; }*/ } else if(command == "BUSES_FOR_STOP") { const auto quantity = bus_seq.size(); bool doYouFind = false; for(unsigned int i=0; i<quantity; ++i) { for(const auto& j : buses[bus_seq[i]]) { if(j == busstop) { doYouFind = true; cout << bus_seq[i] << " "; } } } if(!doYouFind) cout << "No stop"; cout << "\n"; } else if(command == "NEW_BUS") { unsigned int stop_count; string new_stop; bus_seq.push_back(busstop); cin >> stop_count; while(stop_count) { cin >> new_stop; buses[busstop].push_back(new_stop); --stop_count; } } } --q; } // system("pause"); getchar(); return 0; } Решение от янды: Пожалуй, самое сложное в этой задаче — внимательно прочитать условие и аккуратно реализовать все его требования, выбрав при этом правильные контейнеры. Поскольку необходимо было получать как список остановок для конкретного автобуса, так и список автобусов для конкретной остановки, логичнее всего было определить два словаря — buses_to_stops и stops_to_buses со строковыми ключами и значениями типа vector<string>. Ответы на большинство запросов вынесем в отдельные функции: это позволит повысить читаемость кода. Заметьте, что при этом не всегда удаётся передавать словари по константным ссылкам: это происходит из-за того, что использование квадратных скобок (например, в коде stops_to_buses[stop]) теоретически может изменить словарь. В этой ситуации стоило бы использовать метод at вместо квадратных скобок — мы рассмотрим его в следующем курсе. #include <iostream> #include <string> #include <map> #include <vector> using namespace std; // ответ на запрос BUSES_FOR_STOP void PrintBusesForStop(map<string, vector<string>>& stops_to_buses, const string& stop) { if (stops_to_buses.count(stop) == 0) { cout << "No stop" << endl; } else { for (const string& bus : stops_to_buses[stop]) { cout << bus << " "; } cout << endl; } } // ответ на запрос STOPS_FOR_BUS void PrintStopsForBus(map<string, vector<string>>& buses_to_stops, map<string, vector<string>>& stops_to_buses, const string& bus) { if (buses_to_stops.count(bus) == 0) { cout << "No bus" << endl; } else { for (const string& stop : buses_to_stops[bus]) { cout << "Stop " << stop << ": ";
// если через остановку проходит ровно один автобус, // то это наш автобус bus, следовательно, пересадки тут нет if (stops_to_buses[stop].size() == 1) { cout << "no interchange"; } else { for (const string& other_bus : stops_to_buses[stop]) { if (bus != other_bus) { cout << other_bus << " "; } } } cout << endl; } } } // ответ на запрос ALL_BUSES void PrintAllBuses(const map<string, vector<string>>& buses_to_stops) { if (buses_to_stops.empty()) { cout << "No buses" << endl; } else { for (const auto& bus_item : buses_to_stops) { cout << "Bus " << bus_item.first << ": "; for (const string& stop : bus_item.second) { cout << stop << " "; } cout << endl; } } } int main() { int q; cin >> q; map<string, vector<string>> buses_to_stops, stops_to_buses; for (int i = 0; i < q; ++i) { string operation_code; cin >> operation_code; if (operation_code == "NEW_BUS") { string bus; cin >> bus; int stop_count; cin >> stop_count;
// с помощью ссылки дадим короткое название вектору // со списком остановок данного автобуса; // ключ bus изначально отсутствовал в словаре, поэтому он автоматически // добавится туда с пустым вектором в качестве значения vector<string>& stops = buses_to_stops[bus]; stops.resize(stop_count);
for (string& stop : stops) { cin >> stop; // не забудем обновить словарь stops_to_buses stops_to_buses[stop].push_back(bus); } } else if (operation_code == "BUSES_FOR_STOP") { string stop; cin >> stop; PrintBusesForStop(stops_to_buses, stop); } else if (operation_code == "STOPS_FOR_BUS") { string bus; cin >> bus; PrintStopsForBus(buses_to_stops, stops_to_buses, bus); } else if (operation_code == "ALL_BUSES") { PrintAllBuses(buses_to_stops); } } return 0; } |
|||||||
Так же в этом разделе:
|
|||||||
![]() |
|||||||
|
|||||||
|