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

Технічні умови. Програма Words2018 читає з пристрою стандартного введення ціле число N у першому рядку - це розмір таблиці, у другому - слово, яке ми

Приклад

 

Введення

6

VAIVA

IKHJQL

ETEFGH

WXUVCY

MIABFG

AOBCSD

ZNJPRD

Виведення

13

 

© LIKT 1998-2018