Бабка та мураха

Складні стосунки між коником та мурахою відображені не лише у відомій байці Крилова. У грузинській народній казці коник рятує мураху, який не вмів плавати, від утоплення у річці. Чи навчився мураха плавати згодом, у фольклорному епосі не повідомляється. Історія про те, як саме коник врятував мураху, — це тема для іншого разу. Ми ж повертаємося до казки тоді, коли вдячний мураха вирішує запросити коника до найкращого ресторану хінкалі у їхньому лісовому домі. У цей момент друзі перебувають на краю лісу, який можна зобразити у вигляді прямокутної сітки розміром M \times N. Кожна клітинка цієї сітки має певну висоту над рівнем моря. Друзі починають шлях з клітинки $(1,1)$, а ресторан знаходиться у протилежному куті у клітинці (M, N). На кожному кроці вони можуть перейти у будь-яку суміжну клітинку лісу. Дві клітинки вважаються суміжними, якщо мають спільну сторону.

Завдання полягає у виборі шляху з мінімальною втомою для них. Однак коник віддає перевагу шляху з меншою кількістю клітин, а мураха — шляху, де максимальна висота для підйому найменша. Початкова та кінцева клітинки входять до маршруту. Обидва друзі, як і належить у казці, наполягають на тому, щоб вибрати маршрут, який більше до вподоби іншому. Оскільки невідомо, хто з них переконає іншого, ми маємо бути готові допомогти їм в обох випадках. Тому необхідно визначити довжину маршруту, тобто кількість клітин (включаючи початок і кінець), а також максимальну висоту на маршруті, для наступних сценаріїв:

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

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