# Djikstra's Algorithm C++, 32ms, a little long but easy follow

• ``````class Solution {

struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1,T2> &p) const {
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
return h1 ^ h2;
}
};

struct Path{
int cost;
string moves;
};
struct Direction{
vector<int> coordinate;
string letter;
Direction(vector<int> coord, string d)
{
coordinate = coord;
letter = d;
}
};

vector<vector<int>> _maze;
vector<int> _hole;
std::unordered_map<std::pair<int, int>,
Path,
pair_hash>  neighbors;
std::unordered_map<std::pair<int, int>,
Path,
pair_hash>  visited;
vector<Direction> directions{Direction(vector<int>{-1,0}, "u"),Direction(vector<int>{1,0}, "d"),Direction(vector<int>{0,-1}, "l"), Direction(vector<int>{0,1}, "r")};

public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
cout << "initializing... ";
_maze = maze;
_hole = hole;

string shortestPath = "impossible";
Path cheapestPath;
cheapestPath.cost = 0;
cheapestPath.moves = "";
neighbors.insert(pair<pair<int, int>, Path>(std::pair<int, int>(ball[0],ball[1]),cheapestPath));
vector<int> nextCheapest = GetCheapestNeighbor();

cout << "Initialized \n";
while(neighbors.size() > 0 && !(nextCheapest[0] == _hole[0] && nextCheapest[1] == _hole[1])  && nextCheapest[0] != -1)
{
//cout << "Cheapest Coordinates are " << nextCheapest[0] << ":" << nextCheapest[1] << "\n";
auto findNeighbor = neighbors.find(pair<int, int>(nextCheapest[0], nextCheapest[1]));
if(findNeighbor != neighbors.end())
{
visit(nextCheapest, findNeighbor->second);
nextCheapest = GetCheapestNeighbor();
}
}
if(nextCheapest[0] == _hole[0] && nextCheapest[1] == _hole[1])
{
auto findNeighbor = neighbors.find(pair<int, int>(nextCheapest[0], nextCheapest[1]));
if(findNeighbor != neighbors.end())
{
shortestPath = findNeighbor->second.moves;
}
}
return shortestPath;
}

vector<int> GetCheapestNeighbor()
{
int nextCheapest = INT_MAX;
string path = "";
vector<int> cheapCoord = {-1,-1};
for(auto neighbor: neighbors)
{
if (neighbor.second.cost < nextCheapest ||
(neighbor.second.cost == nextCheapest &&
neighbor.second.moves.compare(path) < 0))
{
nextCheapest = neighbor.second.cost;
cheapCoord[0]= neighbor.first.first;
cheapCoord[1] =neighbor.first.second;
path = neighbor.second.moves;
}
}
return cheapCoord;
}

void visit(vector<int> ball, Path path)
{
if(neighbors.find(pair<int,int>(ball[0], ball[1])) != neighbors.end())
{
neighbors.erase(pair<int,int>(ball[0], ball[1]));
}
visited.insert(pair<pair<int, int>,
Path>(pair<int,int>(ball[0], ball[1]), path));

for (auto dir : directions)
{
vector<int> ballVisitor = ball;
int dirLength = travelDirection(dir.coordinate, ballVisitor);
// can move in this direction
if(dirLength > 0)
{
// only check it out if not already visited.
if(visited.find(pair<int,int>(ballVisitor[0], ballVisitor[1])) == visited.end())
{
//cout << "Saying hi to neighbor "<< ballVisitor[0] << ":"<< ballVisitor[1];
auto found = neighbors.find(pair<int,int>(ballVisitor[0], ballVisitor[1]));
Path newPath = path;
newPath.cost += dirLength;
newPath.moves += dir.letter;
if(found != neighbors.end())
{

// if cheaper way to get to the neighbor, update it.
if(found->second.cost >newPath.cost ||
(found->second.cost == newPath.cost &&
found->second.moves.compare(newPath.moves) >0)
)
{
//cout << " updating low cost "<< newPath.cost << " on path "<< newPath.moves;
found->second = newPath;
}
}
else
{
neighbors.insert(pair<pair<int, int>, Path>(pair<int,int>(ballVisitor[0], ballVisitor[1]), newPath));
//cout << " new with low cost "<< newPath.cost<< " on path "<< newPath.moves;
}
//cout << "\n";
}
}
}
}

int travelDirection(vector<int> dir, vector<int>& ball)
{
int currentMoves = 0;
vector<int> newCoord;
newCoord.push_back(ball[0]+dir[0]);
newCoord.push_back(ball[1]+dir[1]);
while((newCoord[0]< _maze.size() && newCoord[0] >= 0) &&
(newCoord[1]< _maze[newCoord[0]].size() && newCoord[1] >= 0)
&& _maze[newCoord[0]][newCoord[1]] != 1  &&
ball != _hole)
{
ball = newCoord;
currentMoves++;

newCoord[0] += dir[0];
newCoord[1] += dir[1];
}
return currentMoves;
}
};
``````

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