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

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

เรามีตำแหน่งเริ่มต้นของลูกบอล จุดหมาย และเขาวงกต เราต้องตรวจสอบว่าลูกบอลสามารถหยุดที่จุดหมายได้หรือไม่ เขาวงกตถูกแทนด้วยอาร์เรย์ 2 มิติ โดย 1 แทนกำแพง และ 0 แทนพื้นที่ว่าง ขอบเขตของเขาวงกตเป็นกำแพงทั้งหมด ตำแหน่งเริ่มต้นและจุดหมายถูกแทนด้วยดัชนีแถวและคอลัมน์

เช่น ถ้าอินพุทเป็นเขาวงกตที่แทนด้วยอาร์เรย์ 2 มิติ

ตำแหน่งเริ่มต้นคือ (0, 4) จุดหมายคือ (4, 4) ผลลัพธ์จะเป็น true วิธีที่เป็นไปได้คือ ซ้าย แล้ว ลง แล้ว ขวา

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

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

#include <bits/stdc++.h> using namespace std; class Solution { public:    bool hasPath(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination) {       int n = grid.size();       int m = grid[0].size();       queue<vector<int> > q;       q.push(start);       set<vector<int> > visited;       visited.insert(start);       while (!q.empty()) {          vector<int> curr = q.front();          q.pop();          int x = curr[0];          int y = curr[1];          if (destination[0] == x && destination[1] == y)             return true;          int i = x;          while (i + 1 < n && !grid[i + 1][y])             i++;          if (!visited.count({ i, y })) {             visited.insert({ i, y });             q.push({ i, y });          }          i = x;          while (i - 1 >= 0 && !grid[i - 1][y])             i--;          if (!visited.count({ i, y })) {             visited.insert({ i, y });             q.push({ i, y });          }          i = y;          while (i + 1 < m && !grid[x][i + 1])             i++;          if (!visited.count({ x, i })) {             visited.insert({ x, i });             q.push({ x, i });          }          i = y;          while (i - 1 >= 0 && !grid[x][i - 1])             i--;          if (!visited.count({ x, i })) {             visited.insert({ x, i });             q.push({ x, i });          }       }       return false;    } }; main(){    Solution ob;    vector<vector<int>> 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}};    vector<int> v1 = {0,4}, v2 = {4,4};    cout << (ob.hasPath(v, v1, v2)); }

อินพุท

{{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}

เอาต์พุท

1