เขาวงกต III ใน C++

สมมติว่ามีเขาวงกตที่มีที่ว่างและกำแพง และยังมีลูกบอลอยู่ในเขาวงกตนั้นด้วย ลูกบอลสามารถผ่านช่องว่างได้โดยการหมุนขึ้น (u) ลง (d) ไปทางซ้าย (l) หรือขวา (r) แต่มันจะกลิ้งไปเรื่อย ๆ จนกว่าจะชนกำแพง เมื่อบอลหยุดก็สามารถเลือกทิศทางต่อไปได้ หลุมหนึ่งอยู่ในเขาวงกตนั้นด้วย ลูกบอลจะตกลงไปในหลุมถ้ากลิ้งไปที่หลุม

ดังนั้นถ้าเรามีตำแหน่งลูก ตำแหน่งหลุม และเขาวงกต เราต้องค้นหาว่าลูกบอลจะตกลงไปในหลุมได้อย่างไร โดยการย้ายระยะทางที่สั้นที่สุด ที่นี่ระยะทางถูกกำหนดโดยจำนวนช่องว่างที่ลูกบอลเดินทางตั้งแต่ต้น (ไม่รวม) ถึงหลุม (รวมอยู่ด้วย)

กลับทิศทางการเคลื่อนที่โดยใช้ 'u', 'd', 'l' และ 'r' เนื่องจากอาจมีวิธีที่สั้นที่สุดได้หลายวิธี และผลลัพธ์ควรเป็นวิธีที่เล็กที่สุด ถ้าลูกไปไม่ถึงหลุม แสดงว่า "เป็นไปไม่ได้"

ที่นี่เขาวงกตแสดงด้วยเมทริกซ์ไบนารี 1 หมายถึง กําแพง และ 0 หมายถึง ที่ว่าง. พิกัดลูกและหลุมจะแสดงด้วยดัชนีแถวและคอลัมน์

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 'lul' เมื่อเลื่อนไปทางซ้าย จากนั้นขึ้นแล้วซ้าย ผลลัพธ์อื่นอาจเป็น 'ul' ขึ้นแล้วซ้าย ทั้งสองมีความยาว 6 แต่นั่นไม่ได้เล็กกว่า lul ทางพจนานุกรม

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดประเภทข้อมูลที่เรียกว่า Data ซึ่งจะใช้ระยะทาง สตริง d และพิกัด 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

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• n :=ขนาดแถวของเขาวงกต

• m :=(ถ้า n ไม่ใช่ศูนย์ แสดงว่าขนาด col ของเขาวงกต มิฉะนั้น 0)

• กำหนดลำดับความสำคัญหนึ่งคิว pq

• แทรกข้อมูลใหม่ด้วย (0, ball[0], ball[1], "") ลงใน pq

• กำหนดอาร์เรย์ 2 มิติที่เข้าชมขนาด n x m

• ในขณะที่ (ไม่ใช่ 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 และเขาวงกต[nx + dir[k, 0], ny + dir[k, 1]] คือ 0, ทำ −

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

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

      • (เพิ่ม tempDist ขึ้น 1)

      • ถ้า ok(nx, ny, hole[0], hole[1]) แล้ว −

        • ออกจากวง

    • หากเข้าชม[nx, ny] เป็นศูนย์ ดังนั้น −

      • แทรกข้อมูลใหม่ (dist + tempDist, nx, ny, d + dirst[k]) ลงใน pq

  • กลับ "เป็นไปไม่ได้"

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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