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


  • 0
    M
    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;
        }
    };
    

Log in to reply
 

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