C++ DFS 9ms 14 lines


  • 5
    V

    I am rolling the ball from the stopping point recursively in the down-left-right-up order, and keeping track of the path with the shortest distance. That way, the first discovered path will be lexicographically smallest (if distance is the same). Except the very first roll, the ball is rolled only vertically (down and up) or horizontally (left and right), alternating.

    When the ball stops, I am using the existing maze vector to store the current distance. If the ball was there before, I only continue the search if the current distance is smaller.

    string roll(vector<vector<int>>& maze, int rowBall, int colBall, const vector<int>& hole, 
        int d_row, int d_col, int steps, const string& path, pair<string, int>& res)
    {
        if (steps < res.second) {
            if (d_row != 0 || d_col != 0) { // both are zero for the initial ball position.
                while ((rowBall + d_row) >= 0 && (colBall + d_col) >= 0 && (rowBall + d_row) <  maze.size() 
                    && (colBall + d_col) < maze[0].size() && maze[rowBall + d_row][colBall + d_col] != 1) 
                {
                    rowBall += d_row;
                    colBall += d_col;
                    ++steps;
                    if (rowBall == hole[0] && colBall == hole[1] && steps < res.second) res = {path, steps};
                }
            }
            if (maze[rowBall][colBall] == 0 || steps + 2 < maze[rowBall][colBall]) {
                maze[rowBall][colBall] = steps + 2; // '1' is for the walls.
                if (d_row == 0) roll(maze, rowBall, colBall, hole, 1, 0, steps, path + "d", res);
                if (d_col == 0) roll(maze, rowBall, colBall, hole, 0, -1, steps, path + "l", res);
                if (d_col == 0) roll(maze, rowBall, colBall, hole, 0, 1, steps, path + "r", res);
                if (d_row == 0) roll(maze, rowBall, colBall, hole, -1, 0, steps, path + "u", res);
            }
        }
        return res.first;
    }
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) 
    {
        return roll(maze, ball[0], ball[1], hole, 0, 0, 0, "", pair<string, int>() = {"impossible", INT_MAX});
    }
    

  • 0
    J

    Nice code. Thanks for sharing.


  • 0

    Nice solution to this problem, you prune out those paths with steps >= hole's distance(if can be reached), which reduces lots of redundant search.


Log in to reply
 

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