# Summary of Maze I, II, III

• The Maze I, II and III problems are similar to other 2D matrix problems. The major difference is they can move more than one steps each time. The solutions are pretty similar.

Maze I

``````class Solution {
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
if (destination == start) return true;
int m = maze.size(), n = (m == 0) ? 0 : maze[0].size();
int dirs[5] = {0, 1, 0, -1, 0};
vector<vector<bool>> visited(m, vector<bool>(n, false));
queue<vector<int>> q;
q.push(start);
while(!q.empty())
{
vector<int> ij = q.front(); q.pop();
int i = ij[0], j = ij[1];
if (i == destination[0] && j == destination[1]) return true;
visited[i][j] = true;
for (int d = 0; d < 4; d++)
{
int x = i, y = j;
while(x+dirs[d] >= 0 && x+dirs[d] < m && y+dirs[d+1] >= 0 && y+dirs[d+1] < n && maze[x+dirs[d]][y+dirs[d+1]] == 0)
{
x += dirs[d], y += dirs[d+1];
}
if (!visited[x][y]) q.push(vector<int>{x, y});
}
}
return false;
}
};
``````

Maze II

``````class Solution {
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
if (destination == start) return true;
int m = maze.size(), n = (m == 0) ? 0 : maze[0].size();
int dirs[5] = {0, 1, 0, -1, 0};
vector<vector<int>> dist(m, vector<int>(n, -1));
dist[start[0]][start[1]] = 0;
queue<vector<int>> q;
q.push(start);
while(!q.empty())
{
vector<int> ij = q.front(); q.pop();
int i = ij[0], j = ij[1];
int distance = dist[i][j];
for (int d = 0; d < 4; d++)
{
int step = 0;
int x = i, y = j;
while(x+dirs[d] >= 0 && x+dirs[d] < m && y+dirs[d+1] >= 0 && y+dirs[d+1] < n && maze[x+dirs[d]][y+dirs[d+1]] == 0)
{
step++;
x += dirs[d], y += dirs[d+1];
}
if (dist[x][y] == -1 || dist[x][y] > distance + step) {
dist[x][y] = distance + step;
q.push(vector<int>{x, y});
}
}
}
return dist[destination[0]][destination[1]];
}
};
``````

Maze III

``````class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
int m = maze.size(), n = (m == 0) ? 0 : maze[0].size();
int dirs[5] = {0, 1, 0, -1, 0};
char sd[4] = {'r', 'd', 'l', 'u'};
vector<vector<pair<int, string>>> dist(m, vector<pair<int, string>>(n, {-1, ""}));
dist[ball[0]][ball[1]].first = 0;
queue<vector<int>> q;
q.push(ball);
while(!q.empty())
{
vector<int> ij = q.front(); q.pop();
int i = ij[0], j = ij[1];
int distance = dist[i][j].first;
string s = dist[i][j].second;
for (int d = 0; d < 4; d++)
{
int step = 0;
int x = i, y = j;
string t = s + sd[d];
while(x+dirs[d] >= 0 && x+dirs[d] < m && y+dirs[d+1] >= 0 && y+dirs[d+1] < n && maze[x+dirs[d]][y+dirs[d+1]] == 0)
{
step++;
x += dirs[d], y += dirs[d+1];
if (x == hole[0] && y == hole[1]) break;
}
if (dist[x][y].first == -1 ||
dist[x][y].first > distance + step ||
dist[x][y].first == distance + step && dist[x][y].second > t)
{
dist[x][y].first = distance + step;
dist[x][y].second = t;
q.push(vector<int>{x, y});
}
}
}
return dist[hole[0]][hole[1]].second == "" ? "impossible" : dist[hole[0]][hole[1]].second;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.