Медовий похід#2533

Медовий похід

1 секунда

64 мегабайти

Дуже легка

Емма та її чоловік Ерік проводять медовий місяць у туристичному поході, подорожуючи від однієї хатинки до іншої щодня. На жаль, Ерік не такий витривалий, як Емма, і швидко втомлюється. Емма хоче уникнути серйозних конфліктів на початку їхнього шлюбу (і ще їй потрібен хтось, хто грітиме її вночі), тому вирішує спланувати маршрути так, щоб Еріку було комфортно.

За останні кілька днів Емма помітила, що Ерік втомлюється не стільки від загальної довжини маршруту чи сумарного підйому. Більше за все його виснажує різниця між найвищою та найнижчою висотою за один день подорожі. Емма вважає, що причина у психології — підніматись одного разу з $500$ до $1500$ метрів здається набагато важче, ніж піднятись десять разів з $200$ до $400$ метрів, навіть якщо в другому випадку підйому вдвічі більше.

Маючи карту з позначенням висот, допоможіть Еммі знайти маршрут від верхнього лівого кута (стартова хатинка) до нижнього правого кута (пункт призначення) так, щоб мінімізувати різницю між максимальною та мінімальною висотою на шляху. Пересуватись дозволено лише у чотирьох основних напрямках (без діагоналей).

Вхідні дані

У першому рядку задано кількість сценаріїв. Кожен сценарій починається з числа $n$ ( $2 \leq n \leq 100$ 2 \le n \le 100) — розміру області. Висоти місцевості наведені у вигляді цілих чисел матриці $n \times n$ n \times n $h_{i, j}$ h_{i,j} ( $0 \leq h_{i, j} \leq 200$ 0 \le h_{i,j} \le 200) у $n$ рядках, кожен з яких містить $n$ висот, розділених пробілами.

Вихідні дані

Для кожного сценарію виведіть рядок "Scenario #i:", де $i$ — номер сценарію, починаючи з $1$ . У наступному рядку виведіть одне ціле число — мінімально можливу різницю між найбільшою та найменшою висотою на оптимальному шляху. Кожен сценарій завершуйте порожнім рядком.

Приклади

Приклад 1