Problem Statement:
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 এ পোষাইতে পারব।
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 ।
