# Leetcode 490 Solution

https://leetcode.com/problems/the-maze

## Solution

``````class Solution {
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
int m = maze.size();
int n = maze[0].size();
vector<vector<int>> dists(m, vector<int>(n, INT_MAX));

queue<pair<int, int>> q;
dists[start[0]][start[1]] = 0;
q.push(make_pair(start[0], start[1]));

auto dest = make_pair(destination[0], destination[1]);
while (q.empty() == false)
{
auto pt = q.front();
auto y = pt.first;
auto x = pt.second;
q.pop();

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

for (int t = 0; t < 4; t++)
{
int i = y;
int j = x;

int step = 0;
while (i + dy[t] >= 0 && i + dy[t] < m && j + dx[t] >= 0 && j + dx[t] < n && maze[i + dy[t]][j + dx[t]] == 0)
{
i += dy[t];
j += dx[t];
step++;
}

auto pt = make_pair(i, j);
auto next_dist = dists[y][x] + step;

if (dists[i][j] > next_dist)
{
q.push(pt);
dists[i][j] = next_dist;
}
}
}

return dists[dest.first][dest.second] != INT_MAX;
}
};
``````