مسیرهای پالیندرومیک
Problem
مزرعه جان با شبکه‌ای از N×N فیلدها (2≤N≤18) نشان داده می‌شود که هر کدام با یک حرف الفبا برچسب‌گذاری شده‌اند. به عنوان مثال،
ABCD
BXZX
CDXB
WCBA
هر روز گاو بسی از گوشه سمت چپ بالا به سمت راست پایین می رود و یک سلول را به سمت راست یا یک سلول به پایین می برد. بسی رشته‌ای را که از مسیر او حاصل می‌شود، از حروفی که طی کرده است، یادداشت می‌کند. اگر رشته‌ای که به‌دست می‌آید یک پالیندروم باشد، بسیار ناراحت می‌شود (از ابتدا تا انتها و از انتها به ابتدا یکسان خوانده می‌شود)، زیرا گیج می‌شود که به کدام سمت رفته است.
لطفاً به Besie کمک کنید تا بفهمد که در طول سفرش چند پالیندروم مختلف می تواند تشکیل دهد. روش های مختلف برای تشکیل یک پالیندروم یکسان فقط باید یک بار شمارش شود. به عنوان مثال، در مثال بالا، چندین راه برای تشکیل پالیندروم ABXZXBA وجود دارد، اما تنها 4 پالیندروم مختلف وجود دارد که Besi می تواند ABCDCBA، ABCWCBA، ABXZXBA، ABXDXBA را تشکیل دهد.
فرمت ورودی:
خط اول ورودی شامل N و خطوط N بعدی حاوی N است. < /strong> توضیحات فیلد. هر خط حاوی N کاراکتر در محدوده A..Z.
است.
فرمت خروجی:
تعداد پالیندروم‌های متمایزی را که Besi می‌تواند تشکیل دهد، چاپ کنید.
<بدن>
| ورودی |
خروجی |
|
4
ABCD
BXZX
CDXB
WCBA
|
4 |