Concise C++ BFS solution based on Maze II


  • 1
    J
    class Solution {
    private:
        int dirx[4]={-1, 0, 1, 0};
        int diry[4]={0, -1, 0, 1};
        string dirs[4]={"u", "l", "d", "r"};
    public:
        string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
            int m=maze.size();
            int n=m?maze[0].size():0;
            
            vector<vector<int>> dists(m, vector<int>(n, -1));
            vector<vector<string>> path(m, vector<string>(n, ""));
            
            queue<pair<int, int>> Q;
            Q.push({ball[0], ball[1]});
            dists[ball[0]][ball[1]]=0;
            
            while(!Q.empty())
            {
                auto cur=Q.front();
                Q.pop();
                
                int dist=dists[cur.first][cur.second];
                string curpath=path[cur.first][cur.second];
                for(int i=0; i<4; i++)
                {
                    pair<int, int> tmpcur=cur;
                    int steps=0;
                    while(checkLocation(maze, tmpcur, i))
                    {
                        ++steps;
                        tmpcur=make_pair(tmpcur.first+dirx[i], tmpcur.second+diry[i]);
                        if(tmpcur.first==hole[0] && tmpcur.second==hole[1])
                        {
                            break;
                        }
                    }
                    if(dists[tmpcur.first][tmpcur.second]==-1) //never visited
                    {
                        dists[tmpcur.first][tmpcur.second]=dist+steps;
                        path[tmpcur.first][tmpcur.second]=curpath+dirs[i];
                        Q.push(tmpcur);
                    }
                    else if(dists[tmpcur.first][tmpcur.second]>dist+steps)
                    {
                        dists[tmpcur.first][tmpcur.second]=dist+steps;
                        path[tmpcur.first][tmpcur.second]= curpath+dirs[i];
                        Q.push(tmpcur);
                    }
                    else if(dists[tmpcur.first][tmpcur.second]==dist+steps)
                    {
                        if(checkPath(path[tmpcur.first][tmpcur.second], curpath+dirs[i]))
                            Q.push(tmpcur);
                        
                    }
                }
            }
            
            return path[hole[0]][hole[1]]==""?"impossible":path[hole[0]][hole[1]];
        }
        
        bool checkLocation(vector<vector<int>>& maze, pair<int, int> cur, int i)
        {
            int m=maze.size();
            int n=m?maze[0].size():0;
            
            int x=cur.first+dirx[i];
            int y=cur.second+diry[i];
            
            if(x>=0 && x<m && y>=0 && y<n && maze[x][y]==0)
                return true;
            return false;
        }
        
        bool checkPath(string& path, string newPath)
        {
            if(path>newPath)
            {
                path=newPath;
                return true;
            }
            return false;
        }
    };
    

Log in to reply
 

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