C++ BFS 6ms solution


  • 0
    M

    I use BFS (bellman-ford algorithm actually) to solve this problem
    https://en.wikipedia.org/wiki/Bellman–Ford_algorithm

    About my implementation:

    We can use vector<vector<pair<int, string>>> to store the path-info of every point in matrix:
    [int] is the shortest distance from ball, and [string] is the path

    During BFS, traverse every point in queue(a vector actually), try moving in four direction until hit the wall, and try to update the path-info of the destination. If update succeed, push that point into the queue. Also we have to check if hole is reachable, and update hole's path-info.

    Notice that when we update a point, if current distance is equal to old-value but path is lexicographically smaller, we should also push it to the queue for next-round BFS. This is different from normal Bellman-Ford-algorithm.

    class Solution {
    public:
        bool update(pair<int, string>& old, int dist, const string& path)
        {
            if (old.first > dist)
            {
                old.first = dist;
                old.second = path;
                return true;
            }
            else if (old.first == dist)
            {
                old.second = std::min(old.second, path);
                return true;
            }
            return false;
        }
    
        string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
            int m = maze.size();
            int n = maze[0].size();
            vector<vector<pair<int, string>>> paths(m, vector<pair<int, string>>(n, {INT_MAX, ""}));
            
            vector<pair<int, int>> bfs;
            bfs.push_back({ball[0], ball[1]});
            paths[ball[0]][ball[1]] = {1, ""};
    
            while (!bfs.empty())
            {
                vector<pair<int, int>> tmp;
                
                for (int i = 0; i < bfs.size(); ++i)
                {
                    const int row = bfs[i].first;
                    const int col = bfs[i].second;
                    const int dist = paths[row][col].first;
                    const string& path = paths[row][col].second;
    
                    // try left
                    int new_col = col;
                    while (new_col > 0 && maze[row][new_col - 1] == 0) --new_col;
                    if (new_col != col)
                    {
                        string new_path = path + 'l';
    
                        if (update(paths[row][new_col], dist + (col - new_col), new_path))
                            tmp.push_back({row, new_col});
                        if (row == hole[0] && new_col <= hole[1] && col >= hole[1])
                            update(paths[hole[0]][hole[1]], dist + (col - hole[1]), new_path);
                    }
                    
                    // try right
                    new_col = col;
                    while (new_col < n - 1 && maze[row][new_col + 1] == 0) ++new_col;
                    if (new_col != col)
                    {
                        string new_path = path + 'r';
    
                        if (update(paths[row][new_col], dist + (new_col - col), new_path))
                            tmp.push_back({row, new_col});
                        if (row == hole[0] && new_col >= hole[1] && col <= hole[1])
                            update(paths[hole[0]][hole[1]], dist + (hole[1] - col), new_path);
                    }
                    
                    // try up
                    int new_row = row;
                    while (new_row > 0 && maze[new_row - 1][col] == 0) --new_row;
                    if (new_row != row)
                    {
                        string new_path = path + 'u';
                        
                        if (update(paths[new_row][col], dist + (row - new_row), new_path))
                            tmp.push_back({new_row, col});
                        if (col == hole[1] && new_row <= hole[0] && row >= hole[0])
                            update(paths[hole[0]][hole[1]], dist + (row - hole[0]), new_path);
                    }
                    
                    // try down
                    new_row = row;
                    while (new_row < m - 1 && maze[new_row + 1][col] == 0) ++new_row;
                    if (new_row != row)
                    {
                        string new_path = path + 'd';
                        
                        if (update(paths[new_row][col], dist + (new_row - row), new_path))
                            tmp.push_back({new_row, col});
                        if (col == hole[1] && new_row >= hole[0] && row <= hole[0])
                            update(paths[hole[0]][hole[1]], dist + (hole[0] - row), new_path);
                    }
                }
                bfs = std::move(tmp);
            }
    
            if (paths[hole[0]][hole[1]].first == INT_MAX)
                return "impossible";
            else
                return paths[hole[0]][hole[1]].second;
        }
    };
    

Log in to reply
 

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