Задача Words2018. Квадратна таблиця розмірів NxN заповнюється великими літерами латинського алфавіту Першу літеру алфавіту вставляють у будь-яку вільну клітинку, потім другу і т.д. Після останньої літери алфавіту (якщо є ще порожні клітинки), літери знову починаються від початку алфавіту. Данo слово. Напишіть програму, яка буде знаходити маршрут у таблиці від верхнього лівого поля до правого нижнього, де кожна літера з даного слова з'явиться на шляху хоча б один раз. Порядок літер на маршруті не має значення. Довжина маршруту (кількість відвіданих клітинок, включно х початковою та кінцевою) повинна бути мінімальною. Якщо клітинка кілька разів входить до маршруту, то вона підраховується стільки ж разів. Можливо переходити з одної клітинки в іншу, якщо вони мають спільну сторону, але не можна переходити «знизу вгору», тобто не можна повернутися на попередній рядок. Гарантується, що розв’язок завжди існує.
Технічні умови. Програма Words2018 читає з пристрою стандартного введення ціле число N у першому рядку - це розмір таблиці, у другому - слово, яке ми
|
Приклад |
|
|
Введення 6 VAIVA IKHJQL ETEFGH WXUVCY MIABFG AOBCSD ZNJPRD |
Виведення 13
|