Masala #1203
Connecting game
Pokemon o'yinlari orasida "Connect animals" nomli ajoyib o'yin mavjud. O'yin shartiga ko'ra sizga hayvonlar rasmlari tushirilgan kartalar to'g'ri to'rtburchak ko'rinishida taxlangan holatda beriladi. Siz 2 ta bir xil rasmli kartalarni birlashtirish orqali o'yindan chiqarib yuborishingiz mumkin, hamma kartalarni chiqarib yuborganingizdan keyin o'yin yakuniga yetadi. 2 ta bir xil rasmli kartani birlashtirish uchun kartalar orasidagi yo'lda ko'pi bilan 2 ta burilish bo'lishi mumkin. 2 tadan ko'p bo'lgan holatda yoki kartalar orasida yo'l bo'lmagan holatda kartalarni o'yindan chiqara olmaysiz. Kartalar orasidagi yo'l boshqa karta ustidan o'tishi yoki diagonal bo'yicha o'tishi mumkin emas. O'yinni o'ynab ko'rish uchun link.
Sizga NxM o'lchamdagi o'yin maydoni beriladi. O'yin maydonidagi har bir katak ingliz alifbosining kichik harflari yoki . (nuqta) belgisidan iborat bo'lishi mumkin. Bunda harflar hayvonlarni, . belgisi esa bo'sh katakni ifodalaydi. Bir xil harflar bir xil hayvonlarni ifodalaydi. Shu berilgan o'yin holatida nechta birlashtirish imkoniyati borligini aniqlang.
Birinchi qatorda N va M natural sonlari. (2<=N,M<=10)
Keyingi N ta qatorda M tadan belgi, o'yin maydonidagi holat beriladi.
Berilgan o'yin holatidagi birlashtirish imkoniyatlari soni.
# | input.txt | output.txt |
---|---|---|
1 |
3 3 ... a.a ... |
1 |
2 |
3 3 a.a a.a a.a |
15 |
3 |
1 3 aaa |
3 |