# 25ms C++ DFS solution with path pruning

• The idea is simple. Just try every path and pruning by `round_trip` and `length` check. Comments inline.

``````class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
int m = maze.size();
if (m == 0) return "invalid";
int n = maze[0].size();
vector<string> res;
int len = m * n; // max possible distance
vector<vector<int>> visited(m, vector<int>(n));
visited[ball[0]][ball[1]] = true;
dfs(maze, visited, "", ball[0], ball[1], hole, 0, len, res);
if (res.empty()) return "impossible";
sort(res.begin(), res.end());
return res[0];
}

void dfs(vector<vector<int>>& maze, vector<vector<int>>& visited, string p,
int row, int col, vector<int>& hole, int cur, int& len, vector<string>& path ) {
int m = maze.size();
int n = maze[0].size();
vector<int> inc = { 0, 1, 0, -1, 0 }; // four directions
vector<char> dir = {'r', 'd', 'l', 'u'};
for (int i = 0; i < 4; i++) {
int x = inc[i], y = inc[i+1];
int cur_r = row, cur_c = col;
bool boomerang = false; // help pruning
// rolling to walls in four directions
while (cur_r+x >= 0 && cur_r+x < m && cur_c+y >= 0 && cur_c+y < n && maze[cur_r+x][cur_c+y] == 0) {
cur_r += x;
cur_c += y;
if (visited[cur_r][cur_c]) {
boomerang = true; // we are backing to passed way, it won't be shortest at all
break;
}
// passing the hole, validate and put result
if (cur_r == hole[0] && cur_c == hole[1]) {
cur += abs(cur_r - row) + abs(cur_c - col);
if (cur < len) {
path.clear();
len = cur;
}
if (cur == len) path.push_back(p + dir[i]);
return;
}
}
if (boomerang) continue;
int cur_l = cur + abs(cur_r - row) + abs(cur_c - col);
// proceed if the point is not visited and still possible to get shorter distance
if (!visited[cur_r][cur_c] && cur_l < len) {
visited[cur_r][cur_c] = 1;
dfs(maze, visited, p+dir[i], cur_r, cur_c, hole, cur_l, len, path);
visited[cur_r][cur_c] = 0;
}
}
}
};
``````

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