C++ BFS 6ms solution

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

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

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