Железная дорога
Железные дороги появились в XIX веке и стали первым массовым средством транспорта, способным перевозить грузы и пассажиров на дальние расстояния. Расцвет железнодорожного транспорта произошел во время промышленной революции, когда появилась необходимость в эффективной и надежной системе перевозок.
Источниками вдохновения для создания железных дорог стали учеными механические и инженерные принципы, а также первые удачные опыты использования пароходов для перевозки людей и грузов. Утверждается, что первая железная дорога была построена в 1804 году в Великобритании, хотя некоторые другие страны также претендуют на первенство.
Железные дороги дали огромный толчок развитию экономики и общества. Они позволили перевозить грузы значительно быстрее и эффективнее, чем прежние виды транспорта, такие как лошади и ослы. Через некоторое время железные дороги стали удобным и доступным средством перевозки для множества людей, что привело к росту городов и сельских территорий, а также ускорило процессы индустриализации.
В современном мире железные дороги играют важную роль в международной торговле и перевозках. Они по-прежнему осуществляют грузовые и пассажирские перевозки на большие расстояния, обеспечивая связь между городами, регионами и странами. Благодаря железной дороге можно легко доставить грузы из одной части мира в другую, что способствует развитию мировой экономики и укреплению международных отношений.
Кроме того, развитие железнодорожной инфраструктуры помогает улучшить мобильность населения, особенно в урбанизированных областях. Многие современные города основывают свои системы общественного транспорта на железнодорожных сетях, предоставляя быстрый и удобный способ перемещения для миллионов людей.
Кроме экономической и социальной роли железных дорог, они также играют важную роль в экологической устойчивости. В сравнении с другими видами транспорта, такими как автомобили и самолеты, железные дороги считаются более экологически чистыми, так как они производят меньше выбросов парниковых газов и потребляют меньше топлива на пассажиро-километр или грузо-километр.
В целом, железные дороги являются неотъемлемой частью современного мира, обеспечивая экономический рост, социальную мобильность и экологическую устойчивость. Они имеют стратегическое значение для развития национальных и международных транспортных систем и продолжают играть важную роль в глобальных перевозках.
Задача
Вася Морозов играет в компьютерную игру Transport Tycoon Deluxe, где ему очень нравится быть транспортным магнатом, владеющим сетью железных дорог, соединяющей различные города на карте между собой. Помогите Васе определить, в сколько городов можно попасть из некоторого города, используя его железную дорогу.
Входные данные
В первой строке заданы два числа N и K–общее количество городов и номер города, для которого выполняется подсчет (1 <= N <= 100; 1 <= K<= N). В следующих N строках – матрица из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что между городами с номерами i и j Вася строил дорогу, а 0 – не строил.
Выходные данные
Одно число – количество городов, в которые можно попасть из данного города K.
Пример:
Примечание: Из города 1 можно попасть в город 1, естественно, город 3 и город 2 (через 3).
Решение
Данная задача рационально решается с применением алгоритма обхода графа в глубину. Заведем массив b, который будет определять, можно ли попасть в указанный город. При описании рекурсивной процедуры dfs будем вызывать её только для тех городов, в которых мы еще не побывали. Это убережет нас от «вечной рекурсии».
#include <iostream>
#include <vector>
struct data_map {
int cnt = 0;
std::vector<std::vector<bool>> matrix;
std::vector<bool> used;
};
void print_vector(std::vector<std::vector<bool>> const& matrix) {
for (std::vector<bool> row:matrix) {
for (bool val : row) {
std::cout << val;
}
std::cout << "\n";
}
}
void dfs(int node, data_map &data) { //обход в глубину
data.used[node] = true; //запоминаем вершину как пройденную
data.cnt++; //увеличиваем счетчик посещений
for (int i = 0; i < data.matrix.size(); i++) //проверяем все не посещенные ранее
{
if (data.matrix[node][i] && !data.used[i]) dfs(i, data);
}
}
int main() {
system("chcp 1251>nul");
int n;
int k;
data_map data;
std::cout << "Введите количество городов> ";
std::cin >> n;
std::cout << "Введите номер города для которого выполняется подсчёт> ";
std::cin >>k;
for (int i = 0; i < n; i++) { //установка матрицы смежности
std::vector<bool> v;
for (int j = 0; j < n; j++) {
bool vv;
std::cin >> vv;
v.push_back(vv);
}
data.used.push_back(false);
data.matrix.push_back(v);
}
dfs(--k,data);
print_vector(data.matrix);
std::cout <<"Можно посетить: "<< data.cnt << " г.\n";
system("pause");
}