georggeorg

10.02.2022 10:30

Информатика

Есть ответ 👍

Препятствующая полоса Вышедший пенсию бегун Усейн Олд решил качестве утренней тренировки пройти полосу прешитетвий. Полоса представляет из себя последовательность из и столбиков различной целой высоты. В каждый момент времени Усейн находится на каком-то из столбиков и может переместиться только на соседний с ним.

Усейн уже не молод, поэтому не хочет повредить суставы при прохождении полосы. Перемещение со столбика высоты h на соседний называется безопасным, если его высота находится между h - 3 и h +2 включительно. Если высота нового столбика хотя бы на 4 ниже, то при прыжке есть риск

повредить поги, а если хотя бы на 3 выше - при подъеме можно повредить руки. Также обратить внимание на то, что Усейн может двигаться как в правую, так и в левую сторону

Пом Усейну найти наиболее длинный участок полосы препятствий, который он может безопасно преодолеть. А именно, подберите пару чисел s, t, с максимальным |s-t|, чтобы Усейн мог добраться от s-го столбика до t-го, производя лишь безопасные перемещения

Формат входных данных:

В первой строке ввода через пробел заданы два целых числа m и n - количество следующих строк во вводе и количество столбиков

Следующие m строк задают полосу препятствий в виде матрицы размера m х n. Каждая строка имеет длину n и состоит из симполов “.” и «#». символ означает, что данная клетка ничем не звонят, а «#» - что эта клетка столбиком. Все столбики от уровня земли. Таким образом, если в i-й строке на j-м месте стоит решетка, то и во всех следующих строках на этой позиции будет находиться решетка. Высота каждого столбика задается количеством решеток в соответствующем столбце матрицы. Формат выходных данных

Выведите через пробел два целых числа s и t, обозначающих границы движения Усейна по полосе. Обратите внимание, что направление движения имеет значение, и ответы "s t" и "t s” отличаются.