CF - 1214D - Treasure Island
Problem Description here Problem: সহজ ভাষায় বললে, এই প্রব্লেমে আমাদেরকে একটি গ্রীড দেয়া থাকবে। গ্রীডে দুই ধরণের সেল আছে। একধরনের সেলের উপর দিয়ে যাতায়াত সম্ভব এবং অন্য ধরণের সেলের উপর দিয়ে যাতায়াত সম্ভব নয়। আমাদেরকে বের করতে হবে Upper Left সেল থেকে Lower Right সেলে যাওয়ার জন্য কয়টা পাথ আছে যারা সোর্স এবং ডেস্টিনেশন ব্যাতীত অন্য কোন সেলে মিলিত হয় না। এবং আমরা শুধু নিচে অথবা ডানে মুভ দিতে পারবো। Solution: ১) একটু ভালোভাবে লক্ষ্য করলে বোঝা যায় যে, উপরোল্লিখিত পাথের সংখ্যা হবে সর্বোচ্চ ২। ২) এখন আমরা একটি ডিএফএস ছেড়ে একটা ভ্যালিড পাথ পাওয়া গেলে সেটি ভিজিট করে ফেলবো। ৩) আবারও ডিএফএস ছেড়ে কোন ভ্যালিড পাথ পাওয়া যায় কি না দেখবো। এক্ষেত্রে পূর্বের প্রাপ্ত(যদি পেয়ে থাকি) পাথের কোন সেল ভিজিট করা যাবে না যদি না সেটি সোর্স অথবা ডেস্টিনেশন সেল না হয়। Similar Problem Happy Coding 😊