[tutorial] SPOJ QUEEN - Wandering Queen solution

Problem description:

n x m সাইজের একটি দাবার বোর্ড আছে । বোর্ডে একটি Queen (মন্ত্রী) এর বর্তমান পজিশন ও টার্গেট পজিশন দেয়া আছে । বোর্ডে বিভিন্ন cell এ 4 ধরণের ক্যারেকটার আছে - 

1) S দিয়ে বুঝানো হয়েছে Queen (মন্ত্রী) এর starting পজিশন, 

2) F দিয়ে বুঝানো হয়েছে Queen (মন্ত্রী) এর Final পজিশন, 

3) .(dot) বুঝানো হয়েছে ফাকা cell, যেখানে মুভ দেয়া যাবে ।

4) X দিয়ে বুঝানো হয়েছে নিষিদ্ধ cell ।

আউটপুটে বলতে হবে, Queen টা মিনিমিমাম কতটা মুভ দিয়ে starting cell থেকে final পজিশনে যেতে পারবে ।

Problem Link

সমাধান:

Queen যে কোন cell থেকে ৮ দিকে মুভ দিতে পারে এবং একটি মুভে যে কোন দিকে যত দূর ইচ্ছা যেতে পারে, যতক্ষণ না কোন নিষিদ্ধ cell না পায় ।

যদি কোন Queen (x, y) পজিশনে থাকে, তবেঃ

 ১) সে ডান দিকে (x, y+1), (x, y+2), (x, y+3), ... এভাবে (x, m-1) পজিশন পর্যন্ত যে কোন  cell এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ২) সে বাম দিকে (x, y-1), (x, y-2), (x, y-3), ... এভাবে (x, 0) পজিশন পর্যন্ত যে কোন  cell  এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ৩) সে উপর দিকে (x-1, y), (x-2, y), (x-3, y), ... এভাবে (0, y) পজিশন পর্যন্ত যে কোন  cell  এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ৪) সে নিচ দিকে (x+1, y), (x+2, y), (x+3, y), ... এভাবে (n-1, y) পজিশন পর্যন্ত যে কোন  cell এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ৫) সে lower right corner বরাবর (x+1, y+1), (x+2, y+2), (x+3, y+3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

 ৬) সে lower left corner বরাবর (x+1, y-1), (x+2, y-2), (x+3, y-3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

 ৭) সে upper right corner বরাবর (x-1, y+1), (x-2, y+2), (x-3, y+3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

 ৮) সে upper left corner বরাবর (x-1, y-1), (x-2, y-2), (x-3, y-3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

তাহলে আমরা প্রতি মুভে কারেন্ট পজিশন থেকে ৮ দিকে যত গুলো possible মুভ দেয়া সম্ভব তা এক চালেই দিতে পারি ।

এজন্য আমরা যে cell এ S আছে, সেখান থেকে একটি BFS চালাতে পারি । এখান থেকে এক মুভ দিয়ে ৮ দিকে যে সব cell এ যাওয়া সব cell গুলোকে Queue তে push করে রাখব । শুধু ৮ দিকের adjacent cell গুলো নয়, যত গুলো cell এ যাওয়া যায়, সবগুলোকেই Queue তে পুশ করে রাখব ।

এরপরে সেই একই কাজ । প্রতিবার Queue এর front cell টা নেব, এবং সেখান থেকে এক মুভ দিয়ে ৮ দিকে যে সব cell এ যাওয়া সব cell গুলোকে Queue তে push করে রাখব ।

যখন Target cell পাব, তখন তার distance রিটার্ণ করে দেব ।

কিন্ত এখানে একটি ঝামেলা আছে, তা হলো visited cell কে কন্ট্রোল করা । 

কিরকম ঝামেল ? একটা উদাহরণ দেই - 

উপরের চিত্রে, ৮ x ৮ সাইজের একটি দাবা বোর্ড দেখানো হয়েছে । ডান দিকে row এর নাম্বার, আর নিচে column এর নাম্বার দেয়া আছে ।

মনে কর, শুরুতে Queen টি (৪, ৩) পজিশনে আছে । এখান থেকে সে এক মুভে লাল রেখা চিহ্নিত ঘরগুলোর যে কোন ঘরে যেতে পারে ।

ধর, সে ডান দিকে (৪, ৪) পজিশনে গেল । এখান থেকে নীল রেখা চিহ্নিত ঘরগুলোর যে কোন ঘরে যেতে পারে ।

খেয়াল কর, আমি বামে বা ডানে রেখা টানিনি । কারণ, বামে এবং ডানে সব ঘরই visited হয়ে আছে ।

কিন্তু, (৪, ৫) ঘরটি আগে visited হলেও আবার visit করেছে, কারণ তার নিচের ঘর গুলো এখনো unvisited আছে । সে গুলো visit করতে হলে (৪, ৫) ঘরের উপর দিয়ে নিচে যেতে হবে ।

তাহলে, ব্যাপার টা কী দাড়ালো ? কোন ঘর visited হলেই থামা যাবে না । আবার কোন দিকে সব ঘরই visited হয়ে থাকলে আর visit করে লাভ নেই, এতে করে শুধু শুধু সময় বেশি নেবে ।

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

তাহলে সারমর্ম এই দাড়ালো যে, visited ঘর পেলেই যদি থামি, তবে এর পরের ঘর গুলো visit করা হচ্ছে না, আর visited ঘর পাওয়া সত্ত্বেও visit করতেই থাকলে টাইম কমপ্লেক্সিটিতে কুলাবে না, বা ইনফিনাইট লুপে পড়ে যাবে ।

তাহলে এর থেকে মুক্তির উপায় কী ?

উপায়টা হলো, ঐ যে বললাম, যদি সব ঘরই ভিজিট হয়ে থাকে, তাহলে ভিজিট করার দরকার নেই । যেমন, (৪, ৪) থেকে বামে আর ডানে যাইনি ।

কিন্তু কিভাবে বুঝব, ঐ বরাবর সব ঘরই ভিজিট করা আছে কিনা ?

খেয়াল কর, কোন রো বামে বা ডানে থেকে visit করা একই কথা, কারণ বাম থেকে ডানে যত গুলো ঘরে যাওয়া যাবে, ডান থেকে বামে তত গুলো ঘরেই যাওয়া যাবে ।

একই ভাবে, কোন কলাম উপরে বা নিচে থেকে visit করা একই কথা, কারণ উপরে থেকে নিচে যত গুলো ঘরে যাওয়া যাবে, নিচ থেকে উপরেও তত গুলো ঘরেই যাওয়া যাবে ।

একই কথা কোণাকুনি যাবার ক্ষেত্রেও প্রযোজ্য ।

তাহলে, কোন ঘর ভিজিট করার দিক ৮ নয়, আসলে ৪ ।

১) বাম-ডান বরাবর,

২) উপর-নিচ বরাবর,

৩) কোণাকুনিভাবে upper left বা lower right বরাবর,

৪) কোণাকুনিভাবে upper right বা lower left বরাবর ।

তাহলে, কোন ঘর visit করার সময় যদি আমরা visited array তে ঘরটি কোন দিক থেকে visited হয়েছে, এই তথ্য রাখি তবেই সমস্যাটির সমাধান হয়ে যাবে ।

যেমন, আমরা (৩, ৪) থেকে যখন বামে বা ডানে কোন ঘর visit করেছি, তখন ঐ ঘরটি ১ নাম্বার উপায়ে visit করা হয়েছে এটা রেখে দিলাম । তাহলে পরবর্তীতে আর ১ নাম্বার উপায়ে এর কোন ঘর visit করব না ।

উদাহরণ হিসেবে ধর, আমরা visited array টা এভাবে নিলামঃ bool visited[1005][1005][5];

তাহলে, (৩, ৪) থেকে ডানের যে কোন ঘর (p, q) ভিজিট করার সময় visited[p][q][1] = 1; করে দেব । এরপরে, (৪, ৪) থেকে যখন ডানে (৪, ৫) ভিজিট করতে চাইব, তখন আগেই দেখব visited[4][5][1] = 1 কিনা । যদি 1 হয়ে থাকে, তার মানে এই ঘরটি বাম-ডান বরাবর visit করাই আছে । তাই আর visit করব না।

আর BFS এর শুরুতেই আমরা starting cell এর ৪ টা দিক বরাবরই visited array এর মান 1 করে দেব, কারণ, starting cell থেকে ১ম বারই ৪ দিকের সব cell ভিজিট করব । তাই এই cell এ আর আসার দরকার নেই ।

Code: