Bal Ayı Gəzintisi
Emma, yeni evləndiyi əri Eric ilə bal ayını yürüyüş səfərində keçirir. Onlar hər gün bir kabinədən digərinə doğru yürüyüş edirlər. Təəssüf ki, Eric Emma qədər fit deyil və tez yorulur. Emma, yeni evliliklərini ciddi bir münaqişə ilə başlamaq istəmədiyi üçün (və gecələr onu isti tutacaq birinə ehtiyacı olduğu üçün), növbəti günün yürüyüşlərini Eric üçün çox yorucu olmayacaq şəkildə planlamağa qərar verir.
Son günlərdə Emma ərinin maraqlı bir xüsusiyyətini kəşf edib. Eric, gündəlik yürüyüşün uzunluğundan və ya ümumi çıxmalı olduqları metr sayından çox yorulmur. Əksinə, Eric daha çox, bugünkü marşrutun ən yüksək və ən aşağı nöqtəsi arasındakı fərq nə qədər böyükdürsə, o qədər yorulur. Emma bunun psixoloji səbəblərdən olduğunu düşünür. Bir dəfə 500 metrdən 1500 metrə çıxmaq, 200 metrdən 400 metrə on dəfə çıxmaqdan daha çətin səslənir, baxmayaraq ki, sonuncu halda iki dəfə çox çıxmış olursunuz.
Ərazinin yüksəklik xəritəsi verildikdə, Emma'ya ən yüksək və ən aşağı yüksəklik arasındakı fərqi minimum edən bir yol tapmaqda kömək etməlisiniz ki, Eric çox yorulmasın. Başladıqları kabinə xəritənin sol üst küncündə yerləşir və onların təyinatı xəritənin sağ alt küncüdür. Onlar dörd əsas istiqamət boyunca hərəkət edə bilərlər, amma diaqonal olaraq hərəkət edə bilməzlər.
Giriş verilənləri
Birinci sətir ssenarilərin sayını ehtiva edir. Hər ssenari n (2 ≤ n ≤ 100) rəqəmi ilə başlayır, bu ərazinin ölçüsüdür. Ərazinin yüksəklikləri n×n tam ədədlər matrisi (h_i_{,j}) (0 ≤ h_i_{,j} ≤ 200) olaraq n sətirdə verilir, burada hər sətir n boşluqla ayrılmış yüksəklik ehtiva edir.
Çıxış verilənləri
Hər ssenari üçün çıxış "Ssenari #i:" sətiri ilə başlayır, burada i ssenarinin nömrəsidir və 1 ilə başlayır. Sonra, optimal yoldakı ən yüksək və ən aşağı yüksəklik arasındakı fərqi ehtiva edən tək bir sətir çap edin. Ssenarinin çıxışını boş bir sətirlə tamamlayın.