در آخرین اکتشافات باستان
‌شناسان در سرزمین «کهن»، یک دفترچه بسیار مرموز پیدا شده است. طی تحقیقات بسیار مشخص شد که این دفترچه، دفترچه خاطرات رستم است. پس از ناکام ماندن تلاش باستان‌شناسان برای خواندن خاطرات رستم، مشخص شد که رستم از بیم خوانده شدن خاطراتش، متن این دفترچه را با الگوریتم
های بسیار پیچیده رمزنگاری کرده است و کلید این رمز را در یکی از اهرام «دور» قرار داده است. این کلید امروزه تحت تدابیر شدید امنیتی در موزه «دور باستان» نگهداری می‌شود و این موزه به هیچ وجه حاضر نیست این کلید را در اختیار باستان‌
شناسان سرزمین «کهن» قرار دهد. پس از اصرارهای زیاد باستان
‌شناسان «کهن»، موزه «دور باستان» حاضر شد این کلید را در اختیار آن
ها بگذارد. بنابراین درب سالن محل نگه
داری این کلید را باز کرد تا بروند و این کلید را بردارند. اما باستان‌
شناسان باهوش «کهن» متوجه شدند در مسیر درب سالن تا خود کلید تعدادی تله قرار داده شده است. آنها با تجهیزات پیشرفته‌ی خود، مکان این تله‌ها را پیدا کرده‌اند و اکنون می‌خواهند همه مسیر
های ممکن برای رسیدن به کلید را بررسی کنند و بهترین مسیر را انتخاب کنند.  این سالن به شکل یک جدول $1\times n$ است که در خانه‌ی شماره ۱، باستان‌شناسان «کهن» قرار دارند (با نماد B) و در خانه‌ی شماره $n$، کلید قرار دارد (با نماد K) و در برخی از خانه‌های دیگر تله وجود دارد (با نماد T). اگر باستان‌شناسان وارد خانه‌ی تله‌دار بشوند، به پایین می‌افتند و خوراک کوسه‌ها می‌شوند. باستان‌شناسان «کهن» در هر حرکت می‌توانند یکی از این سه کار را انجام دهند: + یک خانه به جلو بروند. + از خانه جلویی بپرند (مستقیماً به دو خانه جلوتر بروند.) + از دو خانه جلویی بپرند (مستقیماً به سه خانه جلوتر بروند.) برنامه شما باید تعداد همه راه‌های ممکن برای رسیدن باستان‌شناسان به کلید را محاسبه کند. ## ورودی در خط اول، عدد n می‌آید و در خط بعدی نقشه‌ی سالن به شکل یک رشته به طول $n$ از حروف `B` و `T` و `K` و `.` می‌آید. حرف `.` نماد خانه‌های خالی است. مقدار $n$ حداکثر ٢٠٠ خواهد بود. ## خروجی در خروجی تعداد راه‌های ممکن برای رسیدن باستان‌شناسان به کلید را بنویسید. ---------- ## ورودی نمونه ۱ 21 B..T.T....TT.T.T....K ## خروجی نمونه ۱ 198 ---------- ## ورودی نمونه ۲ 5 B..TK ## خروجی نمونه ۲ 3 ---------- ## ورودی نمونه ۳ 30 B..T.....TT..T.T...TTT..T.T..K ## خروجی نمونه ۳ 0 ---------- ## ورودی نمونه ۴ 50 B..T..T.T..TT...T.T..T.TT.T....T.T...TT.T..T....TK ## خروجی نمونه ۴ 93312

حل سؤال در بانک سؤالات