C++ এ ধাঁধা III

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

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

'u', 'd', 'l' এবং 'r' ব্যবহার করে চলমান দিকনির্দেশ ফেরত দিন। যেহেতু বিভিন্ন সংক্ষিপ্ততম উপায় হতে পারে, এবং আউটপুটটি অভিধানিকভাবে সবচেয়ে ছোট উপায় হওয়া উচিত। যদি বলটি গর্তে পৌঁছাতে না পারে তবে "অসম্ভব" প্রদর্শন করুন।

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

সুতরাং, যদি ইনপুট মত হয়

তারপরে আউটপুটটি হবে 'লুল' বাম দিকে সরানো হলে, তারপরে উপরে তারপর বামে, আরেকটি ফলাফল হতে পারে 'উল', উপরে তারপর বামে, উভয়ের দৈর্ঘ্য 6, কিন্তু এটি অভিধানগতভাবে 'লুল' থেকে ছোট নয়

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

• ডেটা নামক একটি ডেটা টাইপ সংজ্ঞায়িত করুন, এটি দূরত্ব, একটি স্ট্রিং ডি এবং x,y সমন্বয় করবে।

• আকারের একটি অ্যারে ডাইর সংজ্ঞায়িত করুন:4 x 2 :={{1, 0}, {0, - 1}, {0, 1}, { - 1, 0}}

• আকারের একটি অ্যারে ডিফাইন করুন:4 :={'d', 'l', 'r', 'u'}

• একটি ফাংশন সংজ্ঞায়িত করুন ok(), এটি x1, y1, x2, y2,

• x1 যদি x2 এর মত হয় এবং y1 y2 এর মত হয়

  তাহলে true রিটার্ন করুন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• n :=গোলকধাঁধার সারির আকার

• m :=(যদি n অ-শূন্য হয়, তাহলে গোলকধাঁধার আকার, অন্যথায় 0)

• একটি অগ্রাধিকার সারি pq

  সংজ্ঞায়িত করুন

• pq এ (0, বল[0], বল[1], "") সহ নতুন ডেটা সন্নিবেশ করুন

• n x m

  আকারের পরিদর্শন করা একটি 2D অ্যারে সংজ্ঞায়িত করুন

• যখন (pq খালি নয়), −

  করুন

  • curr :=pq এর শীর্ষ উপাদান

  • x :=curr.x

  • y :=curr.y

  • dist :=curr.dist

  • d :=curr.d

  • যদি ok(x, y, hole[0], hole[1]), তাহলে −

    • d

      ফেরত দিন

  • পরিদর্শন করেছেন [x, y] :=সত্য

  • pq

    থেকে উপাদান মুছুন

  • আরম্ভ করার জন্য k :=0, যখন k − 4, আপডেট করুন (k 1 দ্বারা বাড়ান), −

    • nx :=x, ny :=y

    • tempDist :=0

    • যখন nx + dir[k, 0] =0 এবং ny + dir[k, 1] =0 এবং maze[nx + dir[k, 0], ny + dir[k, 1]] হল 0, do −

      • nx :=nx + dir[k, 0]

      • ny :=ny + dir[k, 1]

      • (টেম্পডিস্ট 1 দ্বারা বৃদ্ধি করুন)

      • যদি ঠিক থাকে(nx, ny, hole[0], hole[1]), তাহলে −

        • লুপ থেকে বেরিয়ে আসুন

    • যদি পরিদর্শন করা হয় [nx, ny] শূন্য হয়, তাহলে −

      • pq এ নতুন ডেটা (dist + tempDist, nx, ny, d + dirst[k]) সন্নিবেশ করুন

  • "অসম্ভব" ফেরত দিন

উদাহরণ

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

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char dirst[4] = {'d', 'l', 'r', 'u'};
class Solution {
public:
   struct Data {
      int dist;
      string d;
      int x, y;
      Data(int a, int b, int c, string s) {
         d = s;
         dist = a;
         x = b;
         y = c;
      }
   };
   struct Comparator {
      bool operator()(Data a, Data b) {
         return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d);
      }
   };
   bool ok(int x1, int y1, int x2, int y2) { return x1 == x2 && y1 == y2; }
   string findShortestWay(vector<vector<int>> &maze, vector<int>&ball,
      vector<int> &hole) {
         int n = maze.size();
         int m = n ? maze[0].size() : 0;
         priority_queue<vector<Data>, vector<Data>, Comparator> pq;
         pq.push(Data(0, ball[0], ball[1], ""));
         vector<vector<bool>> visited(n, vector<bool>(m));
         while (!pq.empty()) {
            Data curr = pq.top();
            int x = curr.x;
            int y = curr.y;
            int dist = curr.dist;
            string d = curr.d;
            if (ok(x, y, hole[0], hole[1])) {
               return d;
            }
            visited[x][y] = true;
            pq.pop();
            for (int k = 0; k < 4; k++) {
               int nx = x;
               int ny = y;
               int tempDist = 0;
               while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && ny + dir[k][1] < m && ny + dir[k][1] >= 0 && !maze[nx + dir[k][0]][ny + dir[k][1]]) {
                  nx += dir[k][0];
                  ny += dir[k][1];
                  tempDist++;
                  if (ok(nx, ny, hole[0], hole[1]))
                     break;
               }
               if (!visited[nx][ny]) {
                  pq.push(Data(dist + tempDist, nx, ny, d + dirst[k]));
               }
            }
         }
         return "impossible";
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {
      {0, 0, 0, 0, 0},
      {1, 1, 0, 0, 1},
      {0, 0, 0, 0, 0},
      {0, 1, 0, 0, 1},
      {0, 1, 0, 0, 0}};
   vector<int> v1 = {4, 3}, v2 = {0, 1};
   cout << (ob.findShortestWay(v, v1, v2));
}

ইনপুট

vector<vector<int>> v = {{0, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 0}};
vector<int> v1 = {4, 3}, v2 = {0, 1};

আউটপুট

lul