Lightoj 1004 Solution in Bangla

Lightoj 1004 Solution in Bangla

Problem Link: Lightoj 1004

প্রথমেই বলে নেই এটা একটি সহজ DP (Dynamic প্রব্লেম)। Rock Climbing জেনে থাকলে সহজেই এটি করতে পারবে । আর না জেনে থাকলে আগে পড়ে আসলে ভালো  হয় ।  বাংলায় এটা নিয়ে ব্লগ আছে হয়তো । যাই হোক  প্রব্লেম নিয়ে আলোচনায় আসি । এখানে একটি ডায়মন্ড শেপের একটি 2d অ্যারে দেয়া আছে । অ্যারের সেল গুলোতে কলা রাখা আছে ।  একটি বানর তার নিচের দিকের adjacent cell গুলোতে যেতে পারে ।  একটি সেল থেকে অন্য সেলে যাওয়ার সময় বানরটি সেই সেলের সব গুলো কলা খেয়ে নিবে । 

নিচের ছবিতে বুঝা যাচ্ছে বিষয়টা । এখন আমাদের কাজ হলো বানরটি সবচেয়ে বেশি কতটি কলা খেতে পারে সেটি বের করা । আমাদের মনে রাখতে হবে বানরটি নিচের দিকে adjacent সেলেই যেতে পারে শুধু । 

                                                             

এখন উপর থেকে নিচে যাওয়ার সময় আসলে আমরা জানি নাহ কোন পথে গেলে বানরটি বেশি কলা খেতে পারবে । কিন্তু আমরা যদি সব গুলো রাস্তাই চেক করে নেই ,তবেই তো পেয়ে যাবো  কোন পথে আমাদের বেশি কলা আছে । 

এখন মনে করি আমরা এখন [1,1] সেলে আছি । যেখানে ৭টি কলা আছে । এখন এই সেল থেকে আমরা দুটো সেলে যেতে পারবো ([২,১] ,[২,২]) । এখন আমরা যদি কোন ভাবে বের করতে পারি আমাদের [২,১] এ গেলে লাভ হবে নাকি [২,২] গেলে লাভ হবে ,যেহেতু এখন আমাদের যেকোনো একটি পথে যেতে হবে কারণ আমাদের প্রব্লেমে বলাই আছে আমরা শুধু নিচের দিকের adjacent সেলে যেতে পারবো । তাই আমরা আমাদের সেলের নিচের adjacent সব গুল দিয়েই চেক করবো তবেই তো আমরা বের করতে পারবো আমাদের কোন পথে বেশি কলা আছে।   

এটা recursion দিয়েই করা যাবে ।  আশা করি  recursion জানো । না জানলে আগে recursion জেনে আসো ।
Function:

এখানে ডায়মন্ড শেপের জন্য দুটি কন্ডিশন ব্যবহার করতে হয়েছে । আশা করি সেটা বুঝতে পারছো ।  এই ফাংশনটি দিয়ে যদি আমরা প্রদত্ত টেস্ট কেস রান করি আমাদের সঠিক আউটপুট দিবে । কিন্তু এটা দিয়ে যদি তুমি সাবমিট দাও সুন্দর করে একটা TLE খাবে ।  এর কারণ বুঝার জন্য তুমি প্রবলেমটি আবার পড়ো।
এই TLE থেকে মুক্তি পাওয়ার  জন্যই আমাদের DP অ্যারে ব্যবহার করতে হবে । আমরা একই কাজ বারবার করবো নাহ,বলেই DP ব্যবহার করবো । এখানে recursion ব্যবহার করে যে কোড দেখানো আছে সেখানে আমরা প্রতিটি সেলে বার বার যাচ্ছি ।  শুরুতেই , রো আর কলাম প্রিন্ট করে দেখতে পারো । তাই আমরা ফাংশনে আগেই দেখে নিবো এই সেলে আমরা এসেছি কিনা । এসে থাকলে আমরা আর নিচের দিকে যাবো নাহ । কারণ আমরা যদি এই সেলে আগেই একবার ঘুরে থাকি তাহলে এর নিচের সেল গুলোতেও ঘুরে এসেছি এবং আমরা জানি কি পরিমাণ কলা আমরা পেতে পারই এই পথে ।আর  এই জানাটা মনে রাখবো আমরা DP  অ্যারে দিয়ে । নিচের সোর্সকোড দিয়ে দিলাম ।