LOJ - 1005 - Rooks Tutorial

Problem Description Click here

প্রব্লেমটিতে বলা হয়েছে, একটা n*n গ্রীড দেয়া থাকবে। সেখানে k সংখ্যক রুক বসাতে হবে যাতে তারা একে অন্যকে এটাক করতে না পারে। আমরা জানি, গ্রীডের যেকোন সেল রিপ্রেজেন্ট করতে দুইটা ভ্যালু লাগে। একটা সারি নং , অন্যটা কলাম নং। একটা রুক অন্য রুককে তখনই এটাক করে যখন অন্য রুক এর সাথে তার সারি নং অথবা কলাম নং মিলে যায়।

সল্যুশন আইডিয়াঃ 

তার মানে আমাকে এমনভাবে, k সংখ্যক রুক বসাতে হবে যাতে একই সারিতে দুইটা রুক বসতে না পারে এবং একই কলামে দুইটা রুক বসতে না পারে। 

১ম ক্ষেত্রঃ  k>n হলে আমি কোনভাবেই রুকগুলোকে নন-এটাকিং পজিশনে বসাতে পারবো না। যেকোন সারি কিংবা কলাম বরাবর আমাকে একাধিক রুক বসাতেই হবে। তাই, সেক্ষেত্রে এন্সার হবে ০। 

২য় ক্ষেত্রঃ  আমাকে প্রথমে বেছে নিতে হবে যে আমি কোন কোন সারিগুলোতে রুক বসাবো। আর n সংখ্যক সারি থেকে k সংখ্যক সারি বাছাই করা যায় কতো উপায়ে? সেটা নাহয়, তুমিই বের চিন্তা কর।

এবার, সারিতো বেছে নিলাম। সেই সারিগুলোর কোন কোন কলাম বরাবর আমি রুক বসাবো? ১ম সারির ক্ষেত্রে আমার হাতে অপশন আছে n টি কলাম। যেকোনটায় আমি রুক বসাতে পারি। তার মানে আমাকে n টি কলাম থেকে একটি বেছে নিতে হবে।

২য় সারির ক্ষেত্রে আমার হাতে অপশন আছে n-1 টি কলাম। কারণ, আগের সারিতে আমি যেই কলাম ব্যাবহার করছি সেটা আর কখনোই ব্যাবহার করা যাবে না। তার মানে আমাকে n-1 টি কলাম থেকে ১টি বেছে নিতে হবে। 

এভাবে চলতে থাক...

পরিশেষে, মোট উপায় বের করার জন্য প্রতিভাগে পাওয়া মানগুলো গুণ করবো নাকি যোগ করবো? সেটাতো তোমাকেই চিন্তা করতে হবে। যোগ করলে কেন যোগ? গুণ করলে কেন গুণ? সেটা নিয়েও ভাবা দরকার।

Happy Coding -_-