একটি গ্রিডে একটি নির্দিষ্ট কোষে পৌঁছানোর জন্য একটি রোবটের জন্য প্রয়োজনীয় লাফের সংখ্যা খুঁজে বের করার জন্য C++ প্রোগ্রাম

ধরুন, আমাদের h x w মাত্রার একটি গ্রিড আছে। গ্রিডটিকে 'initGrid' নামক একটি 2D অ্যারেতে উপস্থাপন করা হয়, যেখানে গ্রিডের প্রতিটি সেল হয় '#' বা '.' দ্বারা উপস্থাপিত হয়। '#' মানে গ্রিডে একটি বাধা রয়েছে এবং '।' এর মানে হল যে ঘরের মধ্য দিয়ে একটি পথ আছে। এখন, সারি নম্বর x এবং কলাম নম্বর y সহ গ্রিডের একটি সেল 'c'-এ একটি রোবট স্থাপন করা হয়েছে। রোবটটিকে সারি নম্বর p এবং কলাম নম্বর q সহ অন্য একটি সেল 'd'-এ যেতে হবে। কোষের স্থানাঙ্ক c এবং d উভয়ই আমাদের কাছে পূর্ণসংখ্যা জোড়া হিসাবে উপস্থাপিত হয়। এখন, রোবট নিম্নলিখিত উপায়ে এক কোষ থেকে অন্য কোষে যেতে পারে -

• রোবটটি কেবলমাত্র একটি কোষ থেকে অন্য কোষে যেতে পারে যদি এটি যে কোষে যেতে চায় সেটি বর্তমানে যে কোষে রয়েছে তার উল্লম্ব বা অনুভূমিকভাবে অবস্থিত।

• রোবটটি 5×5 অঞ্চলের যেকোন ঘরে লাফ দিতে পারে যার কেন্দ্রটি বর্তমানে এটি অবস্থিত।

• রোবটটি শুধুমাত্র গ্রিডের অন্য কক্ষে যেতে পারে যদি গন্তব্য সেলটিতে কোনো বাধা না থাকে। রোবটও গ্রিড ছেড়ে যেতে পারে না।

গন্তব্যে পৌঁছাতে কত লাফ লাগবে তা আমাদের খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি h =4, w =4, c ={2, 1}, d ={4, 4}, initGrid ={"#...", ".##.", "এর মতো হয়। ..#", "..#."}, তাহলে আউটপুট হবে 1। রোবটকে তার গন্তব্যে পৌঁছানোর জন্য শুধুমাত্র একটি লাফ দিতে হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

N:=100 intger জোড়া s এবং t সংজ্ঞায়িত করুন। আকারের একটি অ্যারে গ্রিড সংজ্ঞায়িত করুন:N. আকারের একটি অ্যারে dst সংজ্ঞায়িত করুন:N x N. একটি স্ট্রাকট নোড সংজ্ঞায়িত করুন যাতে পূর্ণসংখ্যার মান রয়েছে a, b এবং e। a সংজ্ঞায়িত করুন ফাংশন চেক(), এটি a, b, রিটার্ন করবে a>=0 এবং a =0 AND b  dst[nd-এর একটি মান, nd-এর b মান], তারপর:নিম্নলিখিত অংশটিকে উপেক্ষা করুন, ডিফএক্স শুরু করার জন্য পরবর্তী পুনরাবৃত্তিতে যান :=-2, যখন diffx <=2, আপডেট করুন (1 দ্বারা diffx বাড়ান ), do:শুরু করার জন্য diffy :=-2, যখন diffy <=2, আপডেট করুন (diffy 1 দ্বারা বাড়ান), do:tm :=|diffx + |diffy|| nx :=nd + diffx-এর একটি মান, nd + diffy-এর ny =b মান যদি চেক(nx, ny) এবং গ্রিড[nx, ny] '.' এর মতো হয়, তাহলে:w :=(যদি tm> 1, তারপর 1, অন্যথায় 0) যদি dst[nd-এর একটি মান, nd-এর b মান] + w  
উদাহরণ
 

 আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
 
#include নেমস্পেস ব্যবহার করে std;const int INF =1e9;#define N 100int h, w;pairs, t;স্ট্রিং গ্রিড[N];int dst[N ][N];স্ট্রাকট নোড { int a, b, e;}; bool check(int a, int b) { রিটার্ন a>=0 &&a =0 &&b  doubleq; doubleq.push_back({a, b, dst[a][b]}); যখন (!doubleq.empty()) { নোড nd =doubleq.front(); doubleq.pop_front(); যদি (nd.e> dst[nd.a][nd.b]) চালিয়ে যান; for (int diffx =-2; diffx <=2; diffx++) { (int diffy =-2; diffy <=2; diffy++) { int tm =abs(diffx) + abs(diffy); int nx =nd.a + diffx, ny =nd.b + diffy; যদি (চেক(nx, ny) &&grid[nx][ny] =='.') { int w =(tm> 1)? 1 :0; যদি (dst[nd.a][nd.b] + w  c, pair d, স্ট্রিং initGrid[]){ s =c; t =d; s.first--, s.second--, t.first--, t.second--; for(int i =0; i  c ={2, 1}, d ={4, 4}; স্ট্রিং initGrid[] ={"#...", ".##", "...#", "..#."}; সমাধান (c, d, initGrid); রিটার্ন 0;
 
ইনপুট
 
4, 4, {2, 1}, {4, 4}, {"#...", ".##", "...#", "..#"}
 
আউটপুট
 
1