12. Графи. Алгоритми обробки графів.

У попередній розділ На головну | У наступний розділ

1. У неорієнтованому графі потрібно знайти мінімальний шлях між двома вершинами.

Вхідні дані

Першим на вхід надходить число N - кількість вершин в графі (1 ≤ N ≤ 100). Потім записана матриця суміжності (0 позначає відсутність ребра, 1 - наявність ребра). Далі задаються номера двох вершин - початкової і кінцевої.

Вихідні дані

Виведіть спочатку L - довжину найкоротшого шляху (кількість ребер, які потрібно пройти), а потім сам шлях. Якщо шлях має довжину 0, то його виводити не потрібно, достатньо вивести довжину.

2. На шахівниці NxN в клітинці (x1, y1) стоїть голодний шаховий кінь. Він хоче потрапити в клітинку (x2, y2), де росте смачна шахова трава. Яку найменшу кількість ходів він повинен для цього зробити?

Вхідні дані

На вхід програми поступає п'ять чисел: N, x1, y1, x2, y2 (5  N  20, 1  x1, y1, x2, y2  N). Ліва верхня клітинка дошки має координати (1, 1), права нижня - (N, N).

Вихідні дані

У першому рядку виведіть єдине число K - найменшу необхідну кількість ходів коня. У кожному з наступних K + 1 рядків має бути записано 2 числа - координати чергової клітинки в шляху коня.

3. Дана таблиця, що складається з N рядків і M стовпців. У кожній клітині таблиці записано одне з чисел: 0 або 1. Відстанню між клітинами (x1, y1) і (x2, y2) назвемо суму | x1-x2 | + | y1-y2 |. Вам необхідно побудувати таблицю, в клітці (i, j) якої буде записано мінімальна відстань між кліткою (i, j) початкової таблиці і кліткою, в якій записана 1. Гарантується, що хоча б одна 1 в таблиці є.

Вхідні дані

У першому рядку вводяться два натуральних числа N і M, що не перевищують 100. Далі йдуть N рядків по M чисел - елементи таблиці.

Вихідні дані

Потрібно вивести N рядків по M чисел - елементи шуканої таблиці.

4. На стандартній шахівниці (8х8) живуть 2 шахових коня: Червоний і Зелений. Зазвичай вони безтурботно скачуть просторами дошки, пощипуючи шахову травичку, але сьогодні особливий день: у Зеленого коня день народження. Зелений кінь вирішив відсвяткувати цю подію разом з Червоним. Але для здійснення цього прекрасного плану їм потрібно опинитися на одній клітинці. Зауважимо, що Червоний і Зелений шахові коні сильно відрізняються від чорного з білим: вони ходять не по черзі, а одночасно, і якщо виявляються на одній клітинці, ніхто нікого не з'їдає. Скільки ходів їм буде потрібно, щоб насолодитися святом?

Вхідні дані

На вхід програми надходять координати коней, записані за стандартними шаховими правилами (тобто двома символами - маленька латинська літера (від a до h) і цифра (від 1 до 8), що задають стовпець і рядок відповідно).

Вихідні дані

Потрібно вивести найменшу необхідну кількість ходів, або число -1, якщо коні не можуть зустрітися.

5. Іграшковий лабіринт є прозорою пласкою прямокутною коробкою, всередині якої є перешкоди і переміщається кулька. Лабіринт можна нахиляти вліво, вправо, до себе або від себе, після кожного нахилу кулька переміщається в заданому напрямку до найближчої перешкоди або до стінки лабіринту, після чого зупиняється. Метою гри є загнати кульку в один зі спеціальних отворів - виходів. Шарик провалюється в отвір, якщо він зустрічається на його шляху (кулька не зобов'язана зупинятися в отворі).
Спочатку кулька знаходиться в лівому верхньому кутку лабіринту. Гарантується, що рішення існує і лівий верхній кут не зайнятий перешкодою або отвором.

Вхідні дані

У першому рядку вхідного файлу записано числа N і M - розміри лабіринту (цілі позитивні числа, що не перевищують 100). Потім йде N рядків по M чисел в кожному - опис лабіринту. Число 0 в описі означає вільне місце, число 1 - перешкода, число 2 - отвір.

Вихідні дані

Виведіть єдине число - мінімальну кількість нахилів, які необхідно зробити, щоб кулька покинула лабіринт через один з отворів.

6. Студент хоче придумати нову гру з числами. У цій грі від гравців потрібно перетворювати чотиризначні числа що не містять нулів за допомогою наступного дозволеного набору дій:
1. Можна збільшити першу цифру числа на 1, якщо вона не дорівнює 9.
2. Можна зменшити останню цифру на 1, якщо вона не дорівнює 1.
3. Можна циклічно зсунути всі цифри на одну вправо.
4. Можна циклічно зсунути всі цифри на одну вліво.
Наприклад, застосовуючи ці правила до числа 1234, можна отримати числа 2234, 1233, 4123 і 2 341 відповідно. Точні правила гри студент поки не придумав, але поки його цікавить питання, як отримати з одного числа інше за мінімальну кількість операцій.

Вхідні дані

У вхідному файлі міститься два різних чотиризначних числа, кожне з яких не містить нулів.

Вихідні дані

Програма повинна вивести послідовність чотиризначних чисел, що не містять нулів. Послідовність повинна починатися першим з даних чисел і закінчуватися другим з даних чисел, кожне наступне число в послідовності має бути отримане з попереднього числа застосуванням одного з правил. Кількість чисел у послідовності має бути мінімально можливою.

7. Змій Горинич опинився в лабіринті і хоче вибратися з нього якомога швидше. На жаль, після вчорашнього вживання кефіру, ліва голова Змія розуміє погано. Тому Змій Горинич може повертати праворуч і йти прямо, але не може повертати ліворуч і розвертатися на місці. Допоможіть Змію Гориничу визначити довжину найкоротшого шляху до виходу з лабіринту.

Вхідні дані

У першому рядку через пропуск записані числа r і c (4 ≤ r, c ≤ 20) - кількість рядків і стовпців в карті лабіринту. У кожному з наступних r рядків записано по c символів, які задають цю карту. Символ S позначає положення Змія Горинича, символ F - точку виходу з лабіринту, символ X - стінку. Пробілами позначені прохідні клітини. Гарантується, що лабіринт оточений стінами. Перед початком руху Змій Горинич може зорієнтуватися за допомогою одного з 4 напрямків (вгору, вниз, ліворуч або праворуч).

Вихідні дані

Виведіть єдине число - відстань, яку доведеться пройти Змію Гориничу. Гарантується, що він завжди зможе вийти з лабіринту.

8. Карта світу в комп'ютерній грі "Цивілізація" версії 1 являє собою прямокутник, розбитий на квадратики. Кожен квадратик може мати один з кількох можливих рельєфів, для простоти обмежимося трьома видами рельєфів - поле, ліс і вода. Поселенець переміщається по карті, при цьому на переміщення в клітинку, зайняту полем, необхідна одна одиниця часу, на переміщення в ліс - дві одиниці часу, а переміщатися в клітинку з водою не можна.
У вас є один поселенець, ви визначили місце, де потрібно побудувати місто, щоб якомога швидше заволодіти всім світом. Знайдіть маршрут переселенця, що приводить його в місце будівництва міста, що вимагає мінімального часу. На кожному ході переселенець може переміщатися в клітинку, що має спільну сторону з тією клітинкою, де він зараз перебуває.

Вхідні дані

У вхідному файлі записано два натуральних числа N і M, що не перевищують 1000 - розміри карти світу (N - число рядків в карті, M - число стовпців). Потім задані координати початкового положення поселенця x і y, де x - номер рядка, y - номер стролбца на карті (1 ≤ x ≤ N, 1 ≤ y ≤ M), рядки нумеруються зверху вниз, стовпці - зліва направо. Потім аналогічно задаються координати клітини, куди необхідно привести поселенця.
Далі йде опис карти світу у вигляді N рядків, кожен з яких містить M символів. Кожен символ може бути або "." (Крапка), що позначає поле, або "W", що позначає ліс, або "#", що позначає воду. Гарантується, що початкова і кінцева клітини шляху переселенця не є водою.

Вихідні дані

У першому рядку вихідного файлу виведіть кількість одиниць часу, необхідну для переміщення поселенця (переміщення в клітину з полем займає 1 одиницю часу, переміщення в клітину з лісом - 2 одиниці часу). У другому рядку вихідного файлу виведіть послідовність символів, які задають маршрут переселенця. Кожен символ має бути одним з чотирьох наступних: "N" (рух вгору), "E" (рух вправо), "S" (рух вниз), "W" (рух вліво). Якщо таких маршрутів декілька, виведіть будь-який з них.
Якщо дійти з початкової клітини в кінцеву неможливо, виведіть число -1.

9. Дано число X і множину цифр D. Потрібно дописати до X мінімальну кількість цифр з D, щоб отримане число ділилося на k. При цьому число, має бути мінімально можливим.

Вхідні дані

Перший рядок вхідного файлу містить два натуральних числа X і k (1 ≤ X ≤ 105, 2 ≤ k ≤ 105). У другому рядку записано кількість цифр у множині D. У третьому рядку через пропуск записані ці цифри.

Вихідні дані

Єдиний рядок повинен містити мінімальну кількість, отриману з X дописуванням цифр з D і кратне k. Якщо такого числа не існує, виведіть -1.

10. Заданий граф (орграф) у вигляді матриці суміжності. Скласти програму:
а) перевірки, чи є в графі петлі;
б) пошуку в графі ізольованої вершини (не суміжної з іншими);
в) визначення ступеня графа;
г) отримання послідовності ребер.

11. Даний граф (орграф). Скласти опис даних для його представленняі фрагмент програми:
а) отримання найкоротших шляхів і відстаней між усіма вершинами за алгоритмом Флойда і виведення найкоротшого шляху від вершини А до вершини В;
б) отримання матриці зв'язності за алгоритмом Уоршалла і виведення номерів вершин кожної компоненти зв'язності графа.

12. Знайдіть медіану графа, тобто таку його вершину, що сума відстаней від неї до інших вершин мінімальна.

Остання зміна: Monday 23 April 2018 11:31 AM