Bal Ayı Gəzintisi#2533
Emma və əri Erik bal aylarını dağlarda yürüş edərək müxtəlif daxmalarda gecələməklə keçirirlər. Təəssüf ki, Erik Emma qədər yaxşı formada deyil və tez yorulur. Emma nikahlarının əvvəllərində ciddi narazılıq yaranmasından qaçmaq (və həmçinin gecələr onun yanında isti qalacaq birinə ehtiyacı olduğu üçün) marşrutları Erik üçün rahat olacaq şəkildə planlaşdırmaq qərarına gəlir.
Son günlərdə Emma müşahidə edib ki, Erik nə yürüşün ümumi məsafəsindən, nə də ümumi yüksəlişdən çox yorulur. Əslində, gün ərzində marşrut üzrə ən yüksək və ən aşağı hündürlük arasındakı fərq nə qədər böyük olarsa, Erik bir o qədər yorulur. Emma düşünür ki, bu psixoloji səbəblərdən irəli gəlir—bir dəfə 500 metrdən 1500 metrə qalxmaq, on dəfə 200 metrdən 400 metrə qalxmaqdan daha çətin səslənir, hərçənd sonuncu iki dəfə artıq qalxmaq tələb edir.
Sizə yüksəkliklərin verildiyi bir xəritə verilir. Emmaya başlanğıc (sol yuxarı küncdə yerləşən daxma) nöqtəsindən təyinat (sağ aşağı künc) nöqtəsinə elə bir yol tapmağa kömək edin ki, həmin yolda keçilən ən yüksək və ən aşağı yüksəklik arasındakı fərq minimal olsun. Hərəkət yalnız dörd əsas istiqamətdə mümkündür (diaqonallar yoxdur).
The first line contains the number of scenarios. Each scenario starts with a number (2 \le n \le 100), the size of the area. The terrain elevations are given as an n \times n integer matrix h_{i,j} (0 \le h_{i,j} \le 200) on lines, each containing space-separated elevations.
For each scenario, print a line "Scenario #i:", where is the scenario number starting from . On the next line, print a single integer—the minimum possible difference between the highest and lowest elevation on an optimal path. End each scenario's output with a blank line.
Nümunə 1