# 505. The Maze II - CPP - Solution

• ``````// 505. The Maze II
// https://leetcode.com/problems/the-maze-ii/
#include <iostream>
#include <cassert>
#include <climits>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <iterator>
using namespace std;
// BEGIN: https://discuss.leetcode.com/topic/77472/similar-to-the-maze-easy-understanding-java-bfs-solution
class Solution {
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
if (maze.empty()) {
return 0;
}
const int p = maze.size();
if (maze.front().empty()) {
return 0;
}
const int q = maze.front().size();
list<vector<int>> queue;
queue.push_back(start);
const vector<int> dx{-1, 0, 1, 0};
const vector<int> dy{0, -1, 0, 1};
vector<vector<int>> distance(p, vector<int>(q, -1));
distance[start[0]][start[1]] = 0;
while (!queue.empty()) {
const vector<int> frontOfQueue = queue.front();
queue.pop_front();
const int currentX = frontOfQueue[0];
const int currentY = frontOfQueue[1];
const int currentD = distance[currentX][currentY];
for (int i = 0; i < 4; i++) {
int nextX = currentX;
int nextY = currentY;
int nextD = currentD;
while (nextX + dx[i] >= 0 && nextX + dx[i] < p && nextY + dy[i] >= 0 && nextY + dy[i] < q && maze[nextX + dx[i]][nextY + dy[i]] == 0) {
nextX += dx[i];
nextY += dy[i];
nextD++;
}
const vector<int> nextPoint{nextX, nextY};
if (distance[nextX][nextY] < 0) {
queue.push_back(nextPoint);
distance[nextX][nextY] = nextD;
continue;
}
if (nextD < distance[nextX][nextY]) {
queue.push_back(nextPoint);
distance[nextX][nextY] = nextD;
continue;
}
}
}
return distance[destination[0]][destination[1]];
}
};
// END: https://discuss.leetcode.com/topic/77472/similar-to-the-maze-easy-understanding-java-bfs-solution
int main(void) {
Solution solution;
vector<vector<int>> maze;
vector<int> start;
vector<int> destination;
int result = 0;

maze = {{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}};
start = {0, 4};
destination = {4, 4};
result = solution.shortestDistance(maze, start, destination);
assert(12 == result);

maze = {{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}};
start = {0, 4};
destination = {3, 2};
result = solution.shortestDistance(maze, start, destination);
assert(-1 == result);

cout << "\nPassed All\n";
return 0;
}
``````

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