Shortest distance between two point in a grid when you can move all 8 sides from a position
একটি 2D গ্রিডে এক পজিশন থেকে অন্য পজিশনের ক্ষুদ্রতম দূরত্ব বের করতে হবে যখন বর্তমান পজিশন থেকে সম্ভাব্য সকল দিকে(৮ দিকে) মুভ দেয়া যায়।
এমন প্রব্লেম দেখলে অনেকেই এক দেখাতে সল্যুশন বলে দিবে যে একটা 2D BFS চালিয়ে বের করে নিলাম সিম্পল। কিন্তু এই প্রব্লেম টি যখন অন্য কোন প্রব্লেম এর সাবটাস্ক হিসেবে আসবে তখন MLE অথবা TLE খাওয়ার সম্ভাবনা প্রবল।
এক্ষেত্রে এই প্রব্লেম টি O(1) কমপ্লেক্সিটি তে সলভ করা সম্ভব।
আর সেটি হলো P1 (x1,y1) থেকে p2(x2,y2) বিন্ধুর ক্ষুদ্রতম দূরত্ব হচ্ছে
distance = max( abs(x1-x2) , abs(y1-y2) )
Comments
Post a Comment