Железные дороги появились в 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 будем вызывать её только для тех городов, в которых мы еще не побывали. Это убережет нас от «вечной рекурсии».