C++ এ গোলকধাঁধা II

ধরুন ফাঁকা জায়গা এবং দেয়াল সহ একটি গোলকধাঁধায় একটি বল আছে। এখন বলটি উপরে, নীচে, বাম বা ডানে যে কোনও দিক দিয়ে খালি পথ দিয়ে যেতে পারে, তবে দেওয়ালে আঘাত না করা পর্যন্ত এটি ঘূর্ণায়মান বন্ধ করবে না। বল থেমে গেলে পরবর্তী দিক বেছে নিতে পারে।

আমাদের বলের অবস্থান, গন্তব্য এবং গোলকধাঁধা শুরু করতে হবে, বলটি গন্তব্যে থামার জন্য আমাদের সবচেয়ে কম দূরত্ব খুঁজে বের করতে হবে। এখানে দূরত্বটি প্রকৃতপক্ষে বল দ্বারা আচ্ছাদিত খালি কোষের সংখ্যা দ্বারা সংজ্ঞায়িত করা হয়েছে (শুরু অবস্থান সহ, শুরুর অবস্থান বাদ দিয়ে)। যদি গন্তব্যে বল থামানো অসম্ভব হয়, তাহলে ফিরে আসুন -1।

গোলকধাঁধাটি একটি 2D অ্যারে দ্বারা প্রতিনিধিত্ব করা হয়। এখানে 1 প্রাচীর নির্দেশ করে এবং 0 খালি স্থান নির্দেশ করে। গোলকধাঁধার সীমানা সব দেয়াল। শুরু এবং গন্তব্য স্থানাঙ্ক সারি এবং কলাম সূচক দ্বারা প্রতিনিধিত্ব করা হয়।

সুতরাং, যদি ইনপুটটি একটি ধাঁধাঁর মতো হয় যা একটি 2D অ্যারে দ্বারা প্রতিনিধিত্ব করে

0	0	1	0	0
0	0	0	0	0
0	0	0	1	0
1	1	0	1	1
0	0	0	0	0

স্টার্ট পজিশন হল (0, 4) ডেস্টিনেশন পজিশন হল (4, 4), তারপর আউটপুট হবে 12, একটি সম্ভাব্য উপায় হল:বাম থেকে নিচে থেকে বাম থেকে ডান থেকে ডান থেকে নিচে। (1+1+3+1+2+2+2) =12

C++ এ গোলকধাঁধা II

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

n :=সারি গণনা, m :=কলাম গণনা
ret :=অসীম
n x m
অর্ডারের একটি 2D অ্যারে ডিস্ট সংজ্ঞায়িত করুন
একটি সারি q
সংজ্ঞায়িত করুন
q
-এ স্টার্ট সন্নিবেশ করান
dist[start[0], start[1]] :=0
যখন (q খালি নয়), −
করুন
- curr :=q এর প্রথম উপাদান
- q
  থেকে উপাদান মুছুন
- x :=curr[0], y :=curr[1]
- যদি x গন্তব্য [0] এবং y গন্তব্য [1] হিসাবে একই হয়, তাহলে −
  - ret :=সর্বনিম্ন ret এবং dist[x, y]
- currDist :=dist[x, y]
- tempDist :=0
- i :=x
- যখন (i + 1
  - (i 1 দ্বারা বাড়ান)
  - (টেম্পডিস্ট 1 দ্বারা বৃদ্ধি করুন)
- যদি currDist + tempDist
  - dist[i, y] :=currDist + tempDist
  - q
    -এ {i, y } ঢোকান
- i :=x
- tempDist :=0
- যখন (i - 1>=0 এবং গ্রিড[i - 1, y] শূন্য), করো −
  - (টেম্পডিস্ট 1 দ্বারা বৃদ্ধি করুন)
  - (i 1 দ্বারা কমান)
- যদি currDist + tempDist *lt; dist[i, y], তারপর −
  - dist[i, y] :=currDist + tempDist
  - q
    -এ {i, y } ঢোকান
- i :=y
- tempDist :=0
- যখন (i - 1>=0 এবং গ্রিড[x, i - 1] শূন্য), করো −
  - (i 1 দ্বারা কমান)
  - (টেম্পডিস্ট 1 দ্বারা বৃদ্ধি করুন)
- যদি currDist + tempDist
  - dist[x, i] :=currDist + tempDist
  - q
    -এ { x, i } ঢোকান
- i :=y
- tempDist :=0
- যখন (i + 1
  - (i 1 দ্বারা বাড়ান)
  - (টেম্পডিস্ট 1 দ্বারা বৃদ্ধি করুন)
- যদি currDist + tempDist
  - dist[x, i] :=currDist + tempDist
  - q
    -এ { x, i } ঢোকান

রিটার্ন (যদি ret একই হয় inf, তাহলে -1, অন্যথায় ret)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include  namespace ব্যবহার করে std;class Solution {সর্বজনীন:int shortestDistance(vector&grid, vector dist(n, ভেক্টর  q; q. push(শুরু); dist[start[0]][start[1]] =0; যখন(!q.empty()){ ভেক্টর =0 &&!গ্রিড[i - 1][y]){ tempDist++; i--; } if(currDist + tempDist =0 &&!গ্রিড[x][i - 1]){ i--; tempDist++; } if(currDist + tempDist  v ={{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1 ,0,1,1},{0,0,0,0,0}}; ভেক্টর ইনপুট
 <প্রে>{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1 },{0,0,0,0,0}}, {0,4},{4,4}