Masala #ZZHE8XIVZZ
Yangi yerni tozalash
Doniyor uy qurish uchun yer sotib olishni xohlaydi. U hozirgacha bir nechta yer maydonlarini ko'rdi. Har biri to'rtburchak shaklida bo'lib, N qator va M ustundan iborat matritsani tashkil qiladi.
Doniyor yerning barcha qismlarini o'rib chiqishi kerak. Buni bajarish uchun u o't o'rish mashinasidan foydalanadi. U har qanday maydondan o'rimni boshlashi va asosiy yo'nalishlardan biriga qarab harakat qilishi mumkin (yuqoriga, pastga, chapga yoki o'ngga). Mashina faqat oldinga (qo'shni maydonlarga) harakatlanishi yoki 90 graduslik burilish qilishi mumkin.
Maqsad - mashinani minimal burilishlar bilan harakatlantirib, yerning barcha qismlarini o'rish.
Birinchi qatorda K musbat butun soni keltirilgan. Keyingi K qatorning har birida N va M musbat butun sonlari beriladi.
\(1 \le K \le 5 \times 10^4\)
\(1 \le N, M \le 10^6\)
Har bir maydon uchun minimal burilishlar sonini alohida qatorga chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 1 10 10 1 |
0 0 |
| 2 |
3 1 1 3 3 3 4 |
0 4 4 |
| 3 |
2 5 8 6 4 |
8 6 |
Telegram kanalimizga obuna bo'ling