პალინდრომული გზები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2002/03, FALL, GREEN


   ფერმერ ჯონის ძროხებმა მოიწყინეს და ამიტომ გართობის მიზნით ჯონის საბუღალტრო უწყისში პალინდრომების ძიებას შეუდგნენ. პალინდრომები ისეთი რიცხვებია, რომლებიც ჩვეულებრივ და უკუღმა ერთნაირად იკითხებიან. მაგალითად 1234321 (მაგრამ არა1231). პალინდრომების ციფრთა უმცირესი რაოდენობა უდრის 1.

  ჯონის უწყისი ცხრილს წარმოადგენს ზომით NxN (2 <= N <= 20),  და ამ ცხრილის თითოეულ უჯრაში ჩაწერილია ციფრები (0..9). ძროხებს სურთ ცხრილის მომიჯნე უჯრებზე გაავლონ გზა,  ისე  რომ  შესაბამისი  უჯრებიდან  ამოკრეფილი ციფრები პალინდრომი შეადგინონ. მაგალითად ქვემოთ მოყვანილ ცხრილში არჩეული გზის კვალი მოგვცემს პალინდრომს 122221:

1 -2  0   0

      \

3  8  2 =2

      /

3  1  8   9

 

3  4  5  4

     მოყვანილი უწყისის თანახმად არსებობენ სხვა პალინდრომებიც : 000,  121,  131,  1331,  13331, 2002,  (მიიღებიან რამდენიმე ხერხით), 318813, 454, 8338 და ა.შ.   გაითვალისწინეთ, რომ პალინდრომების შედგენისას შესაძლებელია ციკლების გამოყენება გავლილი ციფრების განმეორებით მარშრუტის უკან შებრუნების ხარჯზე (მაგალითად 121, 122221 და 000 ). ოღონდ პალინდრომის მომიჯნე ციფრები არ შეიძლება უწყისის ერთ და იგივე უჯრას წარმოადგენდნენ (ამიტომ მაგალითად 9889, 95559, და 9999999 დაუშვებელ პალინდრომებს წარმოადგენენ). პალინდრომის სიგრძე მისი ციფრების რაოდენობის ტოლია (12221 შეიცავს 5 ციფრს).

    ძროხებს სურთ გაიგონ პალინდრომული გზების შესაძლო რაოდენობა ამ გზების მოცემული L (1 <= L <= 18) სიგრძის მიხედვით. დაწერეთ პროგრამა რომელიც მოცემული უწყისისისა და  L სიგრძის მიხედვით დაითვლის გზების რაოდენობას.   ჩათვალეთ ორჯერ ის პალინდრომული გზა, რომლის შებრუნებული განსხვავებულ მარშრუტს წარმოადგენს. მოყვანილ მაგალითში 122221 ორჯერ უნდა ჩაითვალოს რადგანაც ეს გზა შეიძლება იწყებოდეს იმ  1-ით, რომელიც მდებარეობს უწყისის პირველ სტრიქონში და მთავრდებოდეს ცხრილის მესამე სტრიქონის 1-ით. და პირიქით, შეგიძლიათ დაიწყოთ მესამე სტროქონში განლაგებულ 1-ით და დაამთავროთ იმ 1-ით რომელის მოთავსებულია უწყისის პირველ სტრიქონში. მეორეს მხრივ 949 მხოლოდ ერთხელ უნდა ჩაითვალოს რადგანაც ორივე მიმართულებით განსაზღვრული გზა ერთ და იგივე მარშრუტს წარმოადგენს. ის იწყება ციფრით 9 შემდეგ 4 და ბრუნდება უწყისის იმავე საწყისს უჯრაში, სადაც მდებარეობს 9.

 შესატანი მონაცემები:

* სტრიქონი 1: შეიცავს ჰარით გამოყოფილ ორ მთელს N და L.

* სტრიქონები 2..N+1: თითოეული შეიცავს ჰარით გამოყოფილ N  ცალ ციფრს.

 

გამომავალი ფაილის ფორმატი:

ერთი სტრიქონი ერთი მთელი რიცხვით, რომელიც აღნიშნავს პალინდრომული გზების საერთო რაოდენობას.

 




მაგალითები

შესატანი მონაცემები
3 3 1 2 3 1 2 3 1 2 3 დაკოპირება
გამოსატანი მონაცემები
86 დაკოპირება