Magic In Grid

-

এই পর্বে আমরা খুবই ইন্টারেস্টিং একটি বিষয় নিয়ে আলোচনা করবো। 


মনে করো, তোমাকে একটি  n * m সাইজের গ্রীড দেয়া আছে। গ্রীডের প্রতিটি সেল এর ভ্যালু,

 grid[i][j] = i+j

তাহলে, একটি ৩ * ৩ সাইজের গ্রীড দেখতে যেমন হবেঃ 


একটি মজার বিষয় লক্ষ্য করেছো কী? কোন একটি সেলের ভ্যালু যদি জোড় হয় তবে তার এডজাসেন্ট সেলগুলোর ভ্যালু বিজোড়। আর কোন সেলের ভ্যালু যদি বিজোড় হয় তবে তার এডজাসেন্ট সেলের ভ্যালু জোড়। এখানে দুটি সেল তখনই এডজাসেন্ট বিবেচ্য হবে যখন তারা একটি সাইড শেয়ার করে। 

গ্রীডের এই প্রোপার্টি টা খুবই সিম্পল। কিন্তু, আমরা অনেকেই হয়তো খেয়াল করি নি এর আগে। আর এটি কতোটা গুরুত্বপূর্ণ প্রোপার্টি তা এই প্রব্লেম সলভ করতে গিয়ে অনুধাবন করেছি 😛


হ্যাপি কোডিং 😊

Comments

Post a Comment

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

-
কিছু কথাঃ DP Series এ আমি মূলত  At Coder Educational DP  কন্টেস্টের প্রব্লেমগুলো নিয়ে আলোচনা করবো এবং সেই সাথে ডিপি সল্যুশন প্রিন্ট, ডিপি অপটিমাইজেশনসহ আরো কিছু বিষয় নিয়ে আলোচনা করবো।  এই সিরিজ টি পড়া শুরু করার আগে সবার ব্যাসিক ডিপি সম্পর্কে ধারণা থাকা আবশ্যক।  এজন্য  শাফায়েতের ব্লগ  থেকে ডাইনামিক প্রোগ্রামিং এর সবগুলো পর্ব পড়ে নেয়ার জন্য অনুরোধ করছি।  Problem Description  here Problem: প্রব্লেমটিতে বলা হয়েছে, আমাদেরকে n টি পাথর দেয়া থাকবে। এবং প্রতিটি পাথরের উচ্চতা দেয়া থাকবে।  একটি ব্যাঙ শুরুতে ১নম্বর পাথরে আছে। ব্যাঙ টি একঘর অথবা দুইঘর জাম্প করতে পারে। অর্থাৎ, i তম পাথর থেকে i+1 or i+2 তম পাথরে যেতে পারে। ith থেকে jth পাথরে যেতে তাকে দুইটি স্টোনের উচ্চতার পার্থক্যের সমান টাকা খরচ করতে হয়।  বের করতে হবে n তম পাথরে পৌঁছাতে তাকে সর্বনিম্ন কত খরচ করতে হবে?  Recursive Solution: ১) এই প্রব্লেমের জন্য আমাদের কয়টি স্টেট লাগবে? ভালোভাবে লক্ষ্য করলে বুঝবে শুধুমাত্র পজিশন ই স্টেট হিসেবে রাখা যথেষ্ট।  ২) এরপর, প্রতি পজিশন থেকে আমি একবা...
Read more

Light OJ - 1013 Love Calculator - Tutorial

-
There're two segments in the solution of this problem. 1. To calculate the length of the shortest string you have to calculate the LCS of two given strings. 2. To calculate the total number of unique strings, you've to follow several steps. i. First of all, it'll be a three states DP. State-1 for the current position of the generating string. State-2 for the current position of the given string-1. State-3 for the current position of the given string-2. ii. If(s1[pos1] == s2[pos2]) then you've to take one way Funtion(pos+1,pos1+1,pos2+1) iii. If(s1[pos1] != s2[pos2]) then you've to take possible two way Funtion(pos+1,pos1+1,pos2)+Function(pos+1,pos1,pos2+1). iv. Now, If any of the given string is completely taken, then you've to add the remaining characters of the other string manually. Check, is the current length of generating string is equal to the previously calculated unique string length or not? If yes, that means you've successfully g...
Read more