Masala #GMYSZCUA0C

Xotira 16 MB Vaqt 1000 ms
14

Yangicha 15 o‘yini

\(15\) o‘yinini haqida eshitgan bo‘lsangiz kerak! Biz uni yangi turini o‘ylab topdik.

O‘yinning yangicha turida, \(15\) o‘yini sonlardan emas, ingliz alifbosining katta \(A\) harfidan \(O\) harfigacha bo‘lgan oraliqdagi belgilardan tashkil topgan. Siz o‘yin doskasida shu harflarni tepadagi rasmdagidek holatda ketma-ket jovlashtirganingizdan so‘ng o‘yinda g‘olib hisoblanasiz. Bundan tashqari bo'sh joyga oldingi o'yindagidek faqatgina qo‘shni yacheykadagi harfni emas, ixtiyoriy joydagi harfni keltirib qo'yishingiz mumkin. Bo‘sh joy koordinatasi \((X, Y)\) bo‘lsa va unga olib kelinadi harfning koordinatasi\((X_h,Y_h)\) bo‘lsa, bu harfni bo‘sh joyga olib kelish uchun, koordinatalar orasidagi matxetten masofasicha, ya’ni\(|X − X_h| + |Y−Y_h|\) birlik energiya sarflaysiz.

Sizga yangicha \(15\) o‘yinining boshlang‘ich holati beriladi. Siz bu o‘yinda g‘olib bo'lish uchun eng kamida qancha birlik energiya sarflashi kerak ekanligini hisoblang.


Kiruvchi ma'lumotlar:

Har birida 4 tadan belgi bo‘lgan 4 qator ma’lumot - 15 o‘yinining boshlang‘ich holati beriladi. Bo‘sh joy o‘rniga nuqta kiritiladi.


Chiquvchi ma'lumotlar:

Yangicha 15 o'yinida g'olib bo'lish uchun sarflash kerak bo'ladigan minimal energiyani chiqaring.


Misollar
# input.txt output.txt
1
ABCD
EFGH
IJKL
M.NO
2
2
.BCD
EAGH
IJFL
MNOK
6