Masala #0424
Snake game
Eski telefonlarda "Iloncha" oyinini o'ynaganmisiz? Agar o'ynamagan bo'lsangiz hozir sizga o'yin qoidalarini tanishtiraman.
1. Dastlab iloncha 1 birlik uzunlikka ega bo'ladi.
2. Har bir yeyilgan olmachalar uchun uning uzunligi 1 birlikka oshib boradi.
3. Yangi qo'shiladigan ilonchaning bo'lagi, uning oxirgi bo'lagining harakat yo'nalishiga mos ravishta va shu bo'lak ketidan joy oladi.
4. Iloncha yo'lida to'siq bo'lmagan hollarda o'ngga, chapga, yuqoriga va pastga harakat qila oladi.
Iloncha o'yini \(8 \times 8\) maydonida bo'ladi va iloncha \(1 \times 1\) katakchadan o’yinni boshlaydi. Sizga mos ravishta ketma-ket paydo bo'luvchi N ta olmachalarning kordinatalari beriladi. Ilonchaning vasifangiz barcha olmachalarni yeb bitirish, ammo buning uchun ilonchaning boshi eng kam masofani bosib o’tishi kerak bo'ladi. (Ilonchaning tanasi va maydonning chetki qismlari to'siqlar hisoblanadi)
Birinchi qatorda olmachalar soni \(N\). Keyingi \(N\) ta qatorda esa ketma-ket paydo bo'luvchi olmachalarning kordinatalari \(x_i,y_i\). \((1 \le N \le 10, 1 \le x_i,y_i \le 8)\)
Barcha olmachalarni yeyish uchun ilonchaning boshi sarflaydigan eng qisqa yo'lning uzunligini toping. (masala yechimga ega ekanligi kafolatlanadi.)
# | input.txt | output.txt |
---|---|---|
1 |
3 1 8 8 8 8 1 |
21 |
2 |
2 8 1 2 1 |
15 |
3 |
2 2 1 8 1 |
7 |