C++의 미로

빈 공간과 벽이 있는 미로에 공이 있다고 가정합니다. 이제 공은 위, 아래, 왼쪽 또는 오른쪽과 같은 방향으로 굴러 빈 경로를 통과할 수 있지만 벽에 부딪힐 때까지 구르는 것을 멈추지 않습니다. 공이 멈추면 다음 방향을 선택할 수 있습니다.

공의 위치, 목적지, 미로를 시작해야 하고 공이 목적지에 멈출 수 있는지 확인해야 합니다. 미로는 하나의 2D 배열로 표현됩니다. 여기서 1은 벽을 나타내고 0은 빈 공간을 나타냅니다. 미로의 경계는 모두 벽입니다. 시작 및 대상 좌표는 행 및 열 인덱스로 표시됩니다.

따라서 입력이 2D 배열로 표현되는 미로와 같은 경우

시작 위치가 (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