Bishops

Problem Statement:

                        আমাদের একটি বিশপ এর current position দিয়ে দেয়া হয়েছে (r1,c1)। এবং আমাদের destination position (r2,c2) ও দেয়া হয়েছে। বিশপটি একটি ইনফিনিট সাইজ chess board এ আসে।আমাদের বলতে হবে বিশপটি তার destination এ পোষাইতে পাড়বে কি না? আর পোষাইতে পাড়লে মিনিমাম কত move এ পোষাইতে পাড়বে।

Solution:

এ প্রব্লেম আমি বহুদিন আগে দেখেছি LOJ এ। কিন্তু অত দিন কোন solution মাথায় আসে নাই।

আজকে same প্রবলেম পাইলাম সিএস আচাডেমীতে। 

লাস্ট দাবা খেলেছি প্রায় ৬ মাস আগে। কিন্তু আজকে প্রব্লেমটা পরতেগিয়ে মাথায় একটা কথা আসল।

কোন বিশপ যদি কাল ঘরে থাকে তাহলে সে কখন সাদায় জেতে পারে না আবার বিশপ যদি সাদা ঘরে থাকে তাহলে সে কখন কাল জেতে পারে না।

এটা যখই মাথায় আসল তখনি বুঝে গেলাম destination এ পোষাইতে পাড়বে কি না তার solution পেয়ে গেসি।

আমি destination এ পোষাইতে পাড়ব যদি same color  হয় current position ও destination position।

এখন এটা check কিভাবে করব?

একটা ২ *৩ board আঁকলাম।

এখনে লক্ষ করলে দেখা যায় যে কোন cell এর r%2==c%2 হলে cellটি  white cell হবে। তা না হলে black cell হবে। 

আমরা পোষাইতে পাড়বে কি না তা পেয়ে গেসি। কিন্তু minimum move আমাদের লাগবে।

তখন আমি একটা ছবি আঁকলাম।

জিনিশটা লক্ষ করার মত হল আমরা যে রঙ এর ঘরে আছি বোর্ডে সেই রঙ এর অন্য কোন ঘর যেতে মাক্সিমাম ২টা move লাগবে। আর ঘরটি current cell er diagonal যদি হয় তাহলে আমরা ১ move এ যেতে পারি।

current cell (3,2) , destination cell (1,4) এ ২ cell diagonal তা হাতে একে দেখলেই বুঝা যায়। যেহেতু diagonal cell তাই ১ টা move চলে যেতে পারব।

current cell (3,2) , destination cell (3,4) এ ২ cell diagonal না। আমরা একটা move দিয়ে (2,3) cell এ চলে যেতে পারব , আর আরেকটা মভে দিয়ে destination cell (3,4) এ চলে যেতে পারব। সব non-diagonal same color cell এ আমরা একই ভাবে ২টা move এ পোষাইতে পারব।

এটাই আমাদের solution :v :v :v ।

এ question পরেছিলাম ১-১.৫ বছর আগে। এ ৩ লাইন এর observation আস্তে লাগে গেছে ১- ১.৫ বছর। জীবন বরই সুন্দর  :D ।