eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Туристичні маршрути

Туристичні маршрути

Туристична фірма вирішила розробити маршрути в гірському районі. Всі маршрути виходять з пункту збору туристів і закінчуватися пунктом від’їзду. Допоможіть розробити якомога більше маршрутів мінімальної довжини. Довжина маршруту -- кількість клітинок, через які він проходить. Задана карта місцевості - масив \textbf{M}×\textbf{N}, в кожній клітинці якої записане натуральне число -- висота місцевості. Туристи зможуть переходити з одного квадрата в інший через спільну сторону, якщо різниця висот не перевищує \textbf{1}. \InputFile У першому рядку записано \textbf{6} чисел \textbf{M}, \textbf{N} - розміри карти, координати пункту збору \textbf{A}, \textbf{B} та координати від’їзду \textbf{C}, \textbf{D} (номер рядка та номер стовпця). Далі записано \textbf{M} рядків по \textbf{N} натуральних чисел - висоти місцевості (значення не перевищують \textbf{100}). \textbf{M}, \textbf{N} = \textbf{1}..\textbf{30}. \OutputFile В єдиному рядку вивести одне число - кількість маршрутів мінімальної довжини, або \textbf{-1}, якщо неможливо прокласти такий маршрут.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
4 5 1 1 2 5
1 2 3 4 6
2 2 2 2 2
3 2 1 2 4
5 2 2 3 1
Вихідні дані #1
3
Автор Жуковський С.С.
Джерело III етап Всеукраїнської олімпіади школярів 2010-2011, 1 тур, м. Житомир