# Concise C++ BFS solution based on Maze II

• ``````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;
}
};
``````

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