빈 공간과 벽이 있는 미로에 공이 있다고 가정합니다. 이제 공은 위, 아래, 왼쪽 또는 오른쪽과 같은 방향으로 굴러 빈 경로를 통과할 수 있지만 벽에 부딪힐 때까지 구르는 것을 멈추지 않습니다. 공이 멈추면 다음 방향을 선택할 수 있습니다.
공의 위치, 목적지, 미로를 시작해야 하고 공이 목적지에 멈출 수 있는지 확인해야 합니다. 미로는 하나의 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)인 경우 출력은 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